Infinite words. Automata, Semigroups, Logic and Games

✍ Scribed by Dominique Perrin, Jean-Eric Pin

• Publisher: Elsevier
• Year: 2004
• Tongue: English
• Leaves: 540
• Category: Library

✦ Table of Contents

Cover
Title page
Preface
I. AUTOMATA AND INFINITE WORDS
1. Introduction
2. Words and trees
3. Rational set.. of Infinite words [3
4. Automata [6 5. Büchi automata
6. Deterministic Büchi automata
7. Muller and Rabin auto mata
7.1. Muller automata
7.2. Rabin automata
7.3. Muller automata with a full table
8. Transition automata
9. McNaughton's theorem
10. Computational comp]exity issues
10.1. From ω-rationa] expressions to Büchi automata and back
10.2. From Muller automata to ω-rational expressions
10.3. From Büchi automata to Rabin automata
10.4. From Rabin automata to Muller automata
10.5. From Rabin automata to Büchi automata
10.6. From Streett automata to Büchi automata
10.7. Complexity of algorithms on automata
11. Exercises
11.1. Words and trees
1l,2. Rational sets
11.3. Büchi automata
11.4. Deterministic Büchi automata
11.5. Muller automata
11.6. McNaughton's theorem
12. Notes
II. AUTOMATA AND SEMIGROUPS
1. Introduction
2. Ramseyan factorizations and linked pairs
2.1. Ramseyan factorizations
2.2. Linked pairs
2.3. Ultimate classes
2.4. Idempotent linked pairs
3. Recognition by morphism
3,1. Semigroup morphisms
3.2. Morphisms of ordered semigroups
3.3. Congruence and syntactic order
3.4. Residuals
4. Semigroups and infinite products
4.1. ω-semigroups
4.2. Morphisms of ω-semigroups
4.3. Free structures
5. Wilke A]gebras
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
11.1. Ramseyan factorizations
11.2. Recognition by morphism
11.3, Wilke algebras
11.4. The two modes of recognition
11.5. Syntactic congruence
11.6. Back to McNaughton's theorem
11.7. Prophetic automata
12. Notes
III. AUTOMATA AND TOPOLOGY
1. Introduction
2. Topological spaces
2.1. Countable sets
2.2. General topology
2.3. Metric spaces
2.4. Polish spaces
2.5. Borel sets
3. The space of infinite words
3.1. The topology of A^ω
3.2. Closed sets
3.3. Clopen sets
3.4. The seeond level of the Borel hierarchy
3.5. Compactness
3.6, The Borel hierarchy of A^ω
4. The space of finite or infinite words
5. Borel automata
6. Suslin sets
7. The separation theorem
8. Exercises
8.1. Topological spaces
8.2. The space of infinite words
8.3. The space of finite or infinite words
8.4. Borel automata
9. Notes
IV. GAMES AND STRATEGIES
1. Introduction
2. Infinite games
3. Borel games
3.1. Open games
3.2. Π₂-games
3.3. Martin's theorem
4. Games on graphs
4.1. Simple games
4.2. Winning conditions
4.3. Parity games
4.4. Parity automata
4.5. Rational winning strategies
5. Wadge games
5.1. Wadge lemma
5.2. Rational reduction
6. Exercises
6.1. Borel games
6.2. Infinite games
6.3. Games on graphs
7. Notes
V. WAGNER HIERARCHY
1. Introduction
2. Ordinals
3. Classes of sets
3.1. Wadge classes
3.2. The boolean hierarchy
3.3. Separated and biseparated union
4. Chains
4.1. Chains in automata
4.2. Chains in ω-semigroups
4.3. Chains in finite ω-semigroups
4.4. Equivalence of the detinitions of chains
4.5. The chain hierarchy
5. Superchains
5.1. Superchains in automata
5.2. Superchains in ω-semigroups
5.3. Superchains in finite ω-semigroups
5.4. Equivalence of the definitions of superchains
5.5. The superchain hierarchy
6. The Wagner hierarchy
6.1. The derived automaton
6.2. The Wagner hierarchy
6.3. Biseparated differences
6.4. The standard representatives
7. Exercises
7.1. Classes of sets
7.2. Chains
7.3. Wagner hierarchy
8. Notes
VI. VARIETIES
1. Introduction
2. Varieties of finite or infinite words
2.1. Varieties of ω-semigroups
2.2. Identities
2.3. The varieties theorem
3. Varieties and topology
4. Weak recognition
4.1. Weak recognition by a morphism of ordered semigroups
4.2. Recognition versus weak recognition
4.3. Properties of the strong expansion
5. Extensions of McNaughton's theorem
6. Varieties closed under aperiodic extension
7. Concatenation hierarchies for infinite words
8. Exercises
8.1. Varieties of finite or infinite words
8.2. Varieties and topology
8.3. Weak recognition
8.4. Boolean combinations of deterministic sets
8.5. Varieties closed under aperiodic extension
9. Notes
VII. LOCAL PROPERTIES
1. Introduction
2. Weak recognition
3. Local properties of infinite words
3.1. Properties defined by letters
3.2. Prefixes and suffixes of infinite words
3.3. Factors of infinite words
4. Exercises
4.1. Local properties of finite words
4.2. Factors of infinite words
5. Notes
VIII. AN EXCURSION INTO LOGIC
1. Introduction
2. The formalism of logic
2.1. Syntax
2.2. Semantics
2.3. Logic on words
3. Monadic second-order logic on words
4. First-order logic of the linear order
4.1. First order and star-free sets
4.2. Logical hierarchy
5. First-order logic of tne successor
5.1. Fraïssé-Ehrenfeueht Games
5.2. Characterization of F₁(S)
6. Temporal logic
6.1. Another cnaracterization of star-free sets
6.2. Star-free sets and temporal logic
7. Restricted temporal logic
8. Exercises
8.1. The formalism of logic
8.2. Monadic second-order logic on words
8.3. First-order logic of the linear order
8.4. First-order logic of the successor
8.5. Temporal logic
9. Notes
IX. BI-INFINITE WORDS
1. Introduction
2. Bi-infinite words
3. Determinism
4. Morpnisms
5. Unambiguous automata on bi-infinite words
6. Discrimination
7. Logic on Z
8. Exercises
8.1. Bi-infinite words
8.2. Morphisms
8.3. Discrimination
8.4. Logic on Z
9. Notes
X. INFINITE TREES
1. Introduction
2. Finite and infinite trees
3. Tree automata
3.1. Automata on finite trees
3.2. Büchi tree automata
3.3. Muller tree automata
3.4. Rabin basis theorem
4. Tree automata and games
4.1. Automaton and Pathfinder
4.2. Rabin's tree theorem
4.3. A second proof of Rabin's basis theorem
5. Topology
5.1. The topological space of infinite trees
5.2. Suslin sets
5.3. Recognizablc sets
6. Monadic second order logic of two successors
7. Effective algorithms
8. Exercises
9. Notes
ANNEX A. FINITE SEMIGROUPS
1. Monoids, scmigroups and semirings
1.1. Definitions
1.2. Congruences
1.3. Structure of finite semigroups
2. Grecn relations
3. Transformation semigroups
4. Semidirect product and wreath product
4.1. Definitions
4.2. Basic decomposition results
5. The wreath product principle
5.1. Sequential functions
5.2. Sets recognized by wreath products
6. Notes
ANNEX B. VARIETIES OF FINITE SEMIGROUPS
1. Varieties of algebras
1.1. Birkhoff varieties
1.2. Varieties of finite semigroups
1.3. Profinite algebras
2. The variety theorem
3. Some examples of varieties
4. Star-free sets
4.1. Concatenation hierarchies
4.2. Varieties closed under marked product
5. Local properties of finite words
5.1. Prefixes and suffixes of finite words
5.2. Pactors of finite words
6. Notes
References
List of Tables
List of Figures
Index