Cover -- Contents -- Preface -- Chapter I. AUTOMATA AND INFINITE WORDS -- 1. Introduction -- 2. Words and trees -- 3. Rational sets of infinite words -- 4. Automata -- 5. Büchi automata -- 6. Deterministic Büchi automata -- 7. Muller and Rabin automata -- 8. Transition automata -- 9. McNaughton's theorem -- 10. Computational complexity issues -- 11. Exercises -- 12. Notes -- Chapter II. AUTOMATA AND SEMIGROUPS -- 1. Introduction -- 2. Ramseyan factorizations and linked pairs -- 3. Recognition by morphism -- 4. Semigroups and infinite products -- 5. Wilke Algebras -- 6. Recognition by morphism of?-semigroups -- 7. The two modes of recognition -- 8. Syntactic congruence -- 9. Back to McNaughton's theorem -- 10. Prophetic automata -- 11. Exercises -- 12. Notes -- Chapter III. AUTOMATA AND TOPOLOGY -- 1. Introduction -- 2. Topological spaces -- 3. The space of infinite words -- 4. The space of finite or infinite words -- 5. Borel automata -- 6. Suslin sets -- 7. The separation theorem -- 8. Exercises -- 9. Notes -- Chapter IV. GAMES AND STRATEGIES -- 1. Introduction -- 2. Infinite games -- 3. Borel games -- 4. Games on graphs -- 5. Wadge games -- 6. Exercises -- 7. Notes -- Chapter V. WAGNER HIERARCHY -- 1. Introduction -- 2. Ordinals -- 3. Classes of sets -- 4. Chains -- 5. Superchains -- 6. The Wagner hierarchy -- 7. Exercises -- 8. Notes -- Chapter VI. VARIETIES -- 1. Introduction -- 2. Varieties of finite or infinite words -- 3. Varieties and topology -- 4. Weak recognition -- 5. Extensions of McNaughton's theorem -- 6. Varieties closed under aperiodic extension -- 7. Concatenation hierarchies for infinite words -- 8. Exercises -- 9. Notes -- Chapter VII. LOCAL PROPERTIES -- 1. Introduction -- 2. Weak recognition -- 3. Local properties of infinite words -- 4. Exercises -- 5. Notes -- Chapter VIII. AN EXCURSION INTO LOGIC -- 1. Introduction -- 2. The formalism of logic -- 3. Monadic second-order logic on words -- 4. First-order logic of the linear order -- 5. First-order logic of the successor -- 6. Temporal logic -- 7. Restricted temporal logic -- 8. Exercises -- 9. Notes -- Chapter IX. BI-INFINITE WORDS -- 1. Introduction -- 2. Bi-infinite words -- 3. Determinism -- 4. Morphisms -- 5. Unambiguous automata on bi-infinite words -- 6. Discrimination -- 7. Logic on Z -- 8. Exercises -- 9. Notes -- Chapter X. INFINITE TREES -- 1. Introduction -- 2. Finite and Infinite trees -- 3. Tree automata -- 4. Tree automata and games -- 5. Topology -- 6. Monadic second order logic of two successors -- 7. Effective algorithms -- 8. Exercises -- 9. Notes -- ANNEX A. FINITE SEMIGROUPS -- 1. Monoids.