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

• Corporate Author: SpringerLink (Online service)
• Other Authors: Grädel, Erich (Editor, http://id.loc.gov/vocabulary/relators/edt), Thomas, Wolfgang (Editor, http://id.loc.gov/vocabulary/relators/edt), Wilke, Thomas (Editor, http://id.loc.gov/vocabulary/relators/edt)
• Format: Electronic eBook
• Language: English
• Published: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2002.
• Edition: 1st ed. 2002.
• Series: Lecture Notes in Computer Science, 2500
• Subjects: Computers.; Computer science.; Theory of Computation.; Computer Science, general.

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 c...

Table of Contents:

• ?-Automata
• Infinite Games
• Determinization and Complementation
• Determinization of Büchi-Automata
• Complementation of Büchi Automata Using Alternation
• Determinization and Complementation of Streett Automata
• Parity Games
• Memoryless Determinacy of Parity Games
• Algorithms for Parity Games
• Tree Automata
• Nondeterministic Tree Automata
• Alternating Tree Automata and Parity Games
• Modal ?-Calculus
• Modal ?-Calculus and Alternating Tree Automata
• Strictness of the Modal ?-Calculus Hierarchy
• Monadic Second-Order Logic
• Decidability of S1S and S2S
• The Complexity of Translating Logic to Finite Automata
• Expressive Power of Monadic Second-Order Logic and Modal ?-Calculus
• Tree-like Models
• Prefix-Recognizable Graphs and Monadic Logic
• The Monadic Theory of Tree-like Structures
• Two-Way Tree Automata Solving Pushdown Games
• Guarded Logics
• to Guarded Logics
• Automata for Guarded Fixed Point Logics
• Appendices
• Some Fixed Point Basics.