Author | Khoussainov, Bakhadyr. author |
---|---|
Title | Automata Theory and its Applications [electronic resource] / by Bakhadyr Khoussainov, Anil Nerode |
Imprint | Boston, MA : Birkhรคuser Boston : Imprint: Birkhรคuser, 2001 |
Connect to | http://dx.doi.org/10.1007/978-1-4612-0171-7 |
Descript | XIV, 432 p. online resource |
1. Basic Notions -- 1.1 Sets -- 1.2 Sequences and Tuples -- 1.3 Functions, Relations, Operations -- 1.4 Equivalence Relations -- 1.5 Linearly Ordered Sets -- 1.6 Partially Ordered Sets -- 1.7 Graphs -- 1.8 Induction -- 1.9 Trees and Kรถnigโs Lemma -- 1.10 Countable and Uncountable Sets -- 1.11 Algorithms -- 2 Finite Automata -- 2.1 Two Examples -- 2.2 Finite Automata -- 2.3 Closure Properties -- 2.4 The MyhillโNerode Theorem -- 2.5 The Kleene Theorem -- 2.6 Generalized Finite Automata -- 2.7 The Pumping Lemma and Decidability -- 2.8 Relations and Finite Automata -- 2.9 Finite Automata with Equations -- 2.10 Monadic Second Order Logic of Strings -- 3 Bรผchi Automata -- 3.1 Two Examples -- 3.2 Bรผchi Automata -- 3.3 The Bรผchi Theorem -- 3.4 Complementation for Bรผchi Automata -- 3.5 The Complementation Theorem -- 3.6 Determinism -- 3.7 Mรผller Automata -- 3.8 The McNaughton Theorem -- 3.9 Decidability -- 3.10 Bรผchi Automata and the Successor Function -- 3.11 An Application of the McNaughton Theorem -- 4 Games Played on Finite Graphs -- 4.1 Introduction -- 4.2 Finite Games -- 4.3 Infinite Games -- 4.4 Update Games and Update Networks -- 4.5 Solving Games -- 5 Rabin Automata -- 5.1 Rabin Automata -- 5.2 Special Automata -- 5.3 Game Automata -- 5.4 Equivalence of Rabin and Game Automata -- 5.5 Terminology: Arenas, Games, and Strategies -- 5.6 The Notion of Rank -- 5.7 Open Games -- 5.8 Congruence Relations -- 5.9 Sewing Theorem -- 5.10 Can Mr. (?) Visit C Infinitely Often? -- 5.11 The Determinacy Theorem -- 5.12 Complementation and Decidability -- 6 Applications of Rabin Automata -- 6.1 Structures and Types -- 6.2 The Monadic Second Order Language -- 6.3 Satisfiability and Theories -- 6.4 Isomorphisms -- 6.5 Definability in T and Decidability of S2S -- 6.6 The Structure with ? Successors -- 6.7 Applications to Linearly Ordered Sets -- 6.8 Application to Unary Algebras -- 6.9 Applications to Cantorโs Discontinuum -- 6.10 Application to Boolean Algebras