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 MyhillNerode 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 LinearlyOrdered Sets. - 6. 8 Application to Unary Algebras. - 6. 9 Applications to Cantor's Discontinuum. - 6. 10 Application to Boolean Algebras. Language: English