Reasoning about Online Algorithms with Weighted Automata

被引：27
作者：
Aminof, Benjamin [1 ]
Kupferman, Orna [1 ]
Lampert, Robby [1 ]
机构：
[1] Hebrew Univ Jerusalem, Sch Engn & Comp Sci, IL-91904 Jerusalem, Israel
来源：
ACM TRANSACTIONS ON ALGORITHMS | 2010年 / 6卷 / 02期
关键词：
Algorithms; Theory; Verification; Formal verification; weighted automata; online algorithms;
D O I：
10.1145/1721837.1721844
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We describe an automata-theoretic approach for the competitive analysis of online algorithms. Our approach is based on weighted automata, which assign to each input word a cost in R->= 0. By relating the "unbounded look ahead" of optimal offline algorithms with nondeterminism, and relating the "no look ahead" of online algorithms with determinism, we are able to solve problems about the competitive ratio of online algorithms, and the memory they require, by reducing them to questions about determinization and approximated determinization of weighted automata.
引用
收藏
页数：36
相关论文
共 24 条
[1]   PRINCIPLES OF OPTIMAL PAGE REPLACEMENT [J].
AHO, AV ;
DENNING, PJ ;
ULLMAN, JD .
JOURNAL OF THE ACM, 1971, 18 (01) :80-&
[2]  
[Anonymous], 1998, Online Computation and Competitive Analysis
[3]  
[Anonymous], 2004, The SPIN Model Checker-Primer and Reference Manual
[4]  
Ball T, 2004, LECT NOTES COMPUT SC, V2999, P1
[5]   Trackless online algorithms for the server problem [J].
Bein, WW ;
Larmore, LL .
INFORMATION PROCESSING LETTERS, 2000, 74 (1-2) :73-79
[6]   ON THE POWER OF RANDOMIZATION IN ONLINE ALGORITHMS [J].
BENDAVID, S ;
BORODIN, A ;
KARP, R ;
TARDOS, G ;
WIGDERSON, A .
ALGORITHMICA, 1994, 11 (01) :2-14
[7]  
Borodin A., 1987, P 19 ANN ACM S THEOR, P373
[8]   SYMBOLIC MODEL CHECKING - 1020 STATES AND BEYOND [J].
BURCH, JR ;
CLARKE, EM ;
MCMILLAN, KL ;
DILL, DL ;
HWANG, LJ .
INFORMATION AND COMPUTATION, 1992, 98 (02) :142-170
[9]  
Chakrabarti A, 2005, LECT NOTES COMPUT SC, V3725, P50
[10]  
Chrobak M., 1991, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, P11
123