Infinite Words (eBook)

Automata, Semigroups, Logic and Games

Dominique Perrin, Jean-Eric Pin (Autoren)

eBook Download: PDF

2004 | 1. Auflage
550 Seiten
Elsevier Science (Verlag)
978-0-08-052564-8 (ISBN)

Infos

Infinite Words is an important theory in both Mathematics and Computer Sciences. Many new developments have been made in the field, encouraged by its application to problems in computer science. Infinite Words is the first manual devoted to this topic.

Infinite Words explores all aspects of the theory, including Automata, Semigroups, Topology, Games, Logic, Bi-infinite Words, Infinite Trees and Finite Words. The book also looks at the early pioneering work of B?chi, McNaughton and Sch?tzenberger.

Serves as both an introduction to the field and as a reference book.
Contains numerous exercises desgined to aid students and readers.
Self-contained chapters provide helpful guidance for lectures.

---

Infinite Words is an important theory in both Mathematics and Computer Sciences. Many new developments have been made in the field, encouraged by its application to problems in computer science. Infinite Words is the first manual devoted to this topic.Infinite Words explores all aspects of the theory, including Automata, Semigroups, Topology, Games, Logic, Bi-infinite Words, Infinite Trees and Finite Words. The book also looks at the early pioneering work of Buchi, McNaughton and Schutzenberger.Serves as both an introduction to the field and as a reference book.Contains numerous exercises desgined to aid students and readers.Self-contained chapters provide helpful guidance for lectures.

Inhalt

Cover 1
Contents 6
Preface 14
Chapter I. AUTOMATA AND INFINITE WORDS 18
1. Introduction 18
2. Words and trees 19
3. Rational sets of infinite words 26
4. Automata 29
5. Büchi automata 38
6. Deterministic Büchi automata 44
7. Muller and Rabin automata 48
8. Transition automata 56
9. McNaughton’s theorem 58
10. Computational complexity issues 73
11. Exercises 80
12. Notes 84
Chapter II. AUTOMATA AND SEMIGROUPS 88
1. Introduction 88
2. Ramseyan factorizations and linked pairs 90
3. Recognition by morphism 99
4. Semigroups and infinite products 105
5. Wilke Algebras 110
6. Recognition by morphism of .-semigroups 114
7. The two modes of recognition 118
8. Syntactic congruence 124
9. Back to McNaughton’s theorem 130
10. Prophetic automata 135
11. Exercises 141
12. Notes 143
Chapter III. AUTOMATA AND TOPOLOGY 146
1. Introduction 146
2. Topological spaces 147
3. The space of infinite words 157
4. The space of finite or infinite words 170
5. Borel automata 177
6. Suslin sets 181
7. The separation theorem 190
8. Exercises 193
9. Notes 198
Chapter IV. GAMES AND STRATEGIES 200
1. Introduction 200
2. Infinite games 201
3. Borel games 203
4. Games on graphs 209
5. Wadge games 220
6. Exercises 223
7. Notes 225
Chapter V. WAGNER HIERARCHY 228
1. Introduction 228
2. Ordinals 229
3. Classes of sets 232
4. Chains 236
5. Superchains 247
6. The Wagner hierarchy 263
7. Exercises 272
8. Notes 276
Chapter VI. VARIETIES 278
1. Introduction 278
2. Varieties of finite or infinite words 280
3. Varieties and topology 285
4. Weak recognition 290
5. Extensions of McNaughton’s theorem 304
6. Varieties closed under aperiodic extension 308
7. Concatenation hierarchies for infinite words 309
8. Exercises 316
9. Notes 318
Chapter VII. LOCAL PROPERTIES 320
1. Introduction 320
2. Weak recognition 321
3. Local properties of infinite words 325
4. Exercises 337
5. Notes 339
Chapter VIII. AN EXCURSION INTO LOGIC 340
1. Introduction 340
2. The formalism of logic 342
3. Monadic second-order logic on words 353
4. First-order logic of the linear order 359
5. First-order logic of the successor 369
6. Temporal logic 376
7. Restricted temporal logic 386
8. Exercises 389
9. Notes 391
Chapter IX. BI-INFINITE WORDS 394
1. Introduction 394
2. Bi-infinite words 395
3. Determinism 403
4. Morphisms 408
5. Unambiguous automata on bi-infinite words 413
6. Discrimination 419
7. Logic on Z 422
8. Exercises 423
9. Notes 425
Chapter X. INFINITE TREES 426
1. Introduction 426
2. Finite and Infinite trees 427
3. Tree automata 430
4. Tree automata and games 438
5. Topology 441
6. Monadic second order logic of two successors 443
7. Effective algorithms 445
8. Exercises 446
9. Notes 447
ANNEX A. FINITE SEMIGROUPS 448
1. Monoids, semigroups and semirings 448
2. Green relations 456
3. Transformation semigroups 461
4. Semidirect product and wreath product 464
5. The wreath product principle 471
6. Notes 476
ANNEX B. VARIETIES OF FINITE SEMIGROUPS 478
1. Varieties of algebras 478
2. The variety theorem 488
3. Some examples of varieties 490
4. Star-free sets 494
5. Local properties of finite words 505
6. Notes 511
References 512
List of Tables 536
List of Figures 538
Index 544

Produkt-Details

• Erscheint lt. Verlag: 12.2.2004
• Sprache: englisch
• Themenwelt: Sachbuch/Ratgeber
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Mathematik / Informatik ► Mathematik ► Algebra
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre
• Themenwelt: Naturwissenschaften
• Themenwelt: Technik
• ISBN-10: 0-08-052564-4 / 0080525644
• ISBN-13: 978-0-08-052564-8 / 9780080525648