Automata Logics, and Infinite Games: A Guide to Current Research

Berndt Farwer (auth.), Erich Grädel, Wolfgang Thomas, Thomas Wilke (eds.)3540003886, 9783540003885

A central aim and ever-lasting dream of computer science is to put the development of hardware and software systems on a mathematical basis which is both firm and practical. Such a scientific foundation is needed especially for the construction of reactive programs, like communication protocols or control systems.

For the construction and analysis of reactive systems an elegant and powerful theory has been developed based on automata theory, logical systems for the specification of nonterminating behavior, and infinite two-person games.

The 19 chapters presented in this multi-author monograph give a consolidated overview of the research results achieved in the theory of automata, logics, and infinite games during the past 10 years. Special emphasis is placed on coherent style, complete coverage of all relevant topics, motivation, examples, justification of constructions, and exercises.

Table of contents :
Front Matter….Pages 2-2
ω-Automata….Pages 3-21
Infinite Games….Pages 23-38
Back Matter….Pages 39-40
Front Matter….Pages 42-42
Determinization of Büchi-Automata….Pages 43-60
Complementation of Büchi Automata Using Alternation….Pages 61-77
Determinization and Complementation of Streett Automata….Pages 79-91
Back Matter….Pages 92-92
Front Matter….Pages 94-94
Memoryless Determinacy of Parity Games….Pages 95-106
Algorithms for Parity Games….Pages 107-129
Back Matter….Pages 130-131
Front Matter….Pages 133-133
Nondeterministic Tree Automata….Pages 135-152
Alternating Tree Automata and Parity Games….Pages 153-167
Back Matter….Pages 168-168
Front Matter….Pages 170-170
Modal μ-Calculus and Alternating Tree Automata….Pages 171-184
Strictness of the Modal μ-Calculus Hierarchy….Pages 185-201
Back Matter….Pages 202-203
Front Matter….Pages 205-205
Decidability of S1S and S2S….Pages 207-230
The Complexity of Translating Logic to Finite Automata….Pages 231-238
Expressive Power of Monadic Second-Order Logic and Modal μ-Calculus….Pages 239-257
Back Matter….Pages 258-259
Front Matter….Pages 261-261
Prefix-Recognizable Graphs and Monadic Logic….Pages 263-283
The Monadic Theory of Tree-like Structures….Pages 285-301
Two-Way Tree Automata Solving Pushdown Games….Pages 303-317
Back Matter….Pages 318-318
Front Matter….Pages 320-320
Introduction to Guarded Logics….Pages 321-341
Automata for Guarded Fixed Point Logics….Pages 343-355
Back Matter….Pages 356-356
Front Matter….Pages 358-358
Some Fixed Point Basics….Pages 359-364