Formal analysis of online algorithms
作者： Benjamin Aminof , Orna Kupferman , Robby Lampert
DOI: 10.1007/978-3-642-24372-1_16
关键词: Competitive analysis 、 Formal verification 、 Reactive system 、 Artificial intelligence 、 Automaton 、 Computer science 、 Word (computer architecture) 、 Analysis of parallel algorithms 、 Online algorithm 、 Look-ahead 、 Theoretical computer science
摘要: In [2], we showed how viewing online algorithms as reactive systems enables the application of ideas from formal verification to the competitive analysis of online algorithms …
springer.com
sci-hub.st 参考文章(34)
Arto Salomaa, Werner Kuich, Semirings, Automata and Languages Springer-Verlag New York, Inc.. ,(1985)
Krishnendu Chatterjee, Thomas A. Henzinger, Barbara Jobstmann, Environment Assumptions for Synthesis international conference on concurrency theory. pp. 147- 161 ,(2008) , 10.1007/978-3-540-85361-9_14
D. Harel, A. Pnueli, On the development of reactive systems Logics and models of concurrent systems. pp. 477- 498 ,(1989) , 10.1007/978-3-642-82453-1_17
Ran El-Yaniv, Allan Borodin, Online Computation and Competitive Analysis ,(1998)
Michael Holtmann, Łukasz Kaiser, Wolfgang Thomas, Degrees of lookahead in regular infinite games foundations of software science and computation structure. pp. 252- 266 ,(2010) , 10.1007/978-3-642-12032-9_18
M. Fujita, P.C. McGeer, J.C.-Y. Yang, Multi-Terminal Binary Decision Diagrams: An Efficient DataStructure for Matrix Representation formal methods. ,vol. 10, pp. 149- 169 ,(1997) , 10.1023/A:1008647823331
Arindam Chakrabarti, Krishnendu Chatterjee, Thomas A. Henzinger, Orna Kupferman, Rupak Majumdar, Verifying Quantitative Properties Using Bound Functions Lecture Notes in Computer Science. pp. 50- 64 ,(2005) , 10.1007/11560548_7
Arto Salomaa, Werner Kuich, Semirings, Automata, Languages ,(2011)
F. R. K. Chung, R. L. Graham, M. E. Saks, A Dynamic location problem for graphs Combinatorica. ,vol. 9, pp. 111- 131 ,(1989) , 10.1007/BF02124674
Dany Breslauer, On competitive on-line paging with lookahead Theoretical Computer Science. ,vol. 209, pp. 365- 375 ,(1998) , 10.1016/S0304-3975(98)00118-2