Elsevier S & T

Infinite Words: Automata, Semigroups, Logic and Games

Perrin, Dominique; Pin, Jean-Éric

In stock
No reviews
85.250 KD inc. VAT
License
Table of contents
  • Cover
  • Contentsv
  • Preface1
  • Chapter I. AUTOMATA AND INFINITE WORDS5
  • 1. Introduction5
  • 2. Words and trees6
  • 3. Rational sets of infinite words13
  • 4. Automata16
  • 5. Büchi automata25
  • 6. Deterministic Büchi automata31
  • 7. Muller and Rabin automata35
  • 8. Transition automata43
  • 9. McNaughton’s theorem45
  • 10. Computational complexity issues60
  • 11. Exercises67
  • 12. Notes71
  • Chapter II. AUTOMATA AND SEMIGROUPS75
  • 1. Introduction75
  • 2. Ramseyan factorizations and linked pairs77
  • 3. Recognition by morphism86
  • 4. Semigroups and infinite products92
  • 5. Wilke Algebras97
  • 6. Recognition by morphism of ω-semigroups101
  • 7. The two modes of recognition105
  • 8. Syntactic congruence111
  • 9. Back to McNaughton’s theorem117
  • 10. Prophetic automata122
  • 11. Exercises128
  • 12. Notes130
  • Chapter III. AUTOMATA AND TOPOLOGY133
  • 1. Introduction133
  • 2. Topological spaces134
  • 3. The space of infinite words144
  • 4. The space of finite or infinite words157
  • 5. Borel automata164
  • 6. Suslin sets168
  • 7. The separation theorem177
  • 8. Exercises180
  • 9. Notes185
  • Chapter IV. GAMES AND STRATEGIES187
  • 1. Introduction187
  • 2. Infinite games188
  • 3. Borel games190
  • 4. Games on graphs196
  • 5. Wadge games207
  • 6. Exercises210
  • 7. Notes212
  • Chapter V. WAGNER HIERARCHY215
  • 1. Introduction215
  • 2. Ordinals216
  • 3. Classes of sets219
  • 4. Chains223
  • 5. Superchains234
  • 6. The Wagner hierarchy250
  • 7. Exercises259
  • 8. Notes263
  • Chapter VI. VARIETIES265
  • 1. Introduction265
  • 2. Varieties of finite or infinite words267
  • 3. Varieties and topology272
  • 4. Weak recognition277
  • 5. Extensions of McNaughton’s theorem291
  • 6. Varieties closed under aperiodic extension295
  • 7. Concatenation hierarchies for infinite words296
  • 8. Exercises303
  • 9. Notes305
  • Chapter VII. LOCAL PROPERTIES307
  • 1. Introduction307
  • 2. Weak recognition308
  • 3. Local properties of infinite words312
  • 4. Exercises324
  • 5. Notes326
  • Chapter VIII. AN EXCURSION INTO LOGIC327
  • 1. Introduction327
  • 2. The formalism of logic329
  • 3. Monadic second-order logic on words340
  • 4. First-order logic of the linear order346
  • 5. First-order logic of the successor356
  • 6. Temporal logic363
  • 7. Restricted temporal logic373
  • 8. Exercises376
  • 9. Notes378
  • Chapter IX. BI-INFINITE WORDS381
  • 1. Introduction381
  • 2. Bi-infinite words382
  • 3. Determinism390
  • 4. Morphisms395
  • 5. Unambiguous automata on bi-infinite words400
  • 6. Discrimination406
  • 7. Logic on Z409
  • 8. Exercises410
  • 9. Notes412
  • Chapter X. INFINITE TREES413
  • 1. Introduction413
  • 2. Finite and Infinite trees414
  • 3. Tree automata417
  • 4. Tree automata and games425
  • 5. Topology428
  • 6. Monadic second order logic of two successors430
  • 7. Effective algorithms432
  • 8. Exercises433
  • 9. Notes434
  • ANNEX A. FINITE SEMIGROUPS435
  • 1. Monoids, semigroups and semirings435
  • 2. Green relations443
  • 3. Transformation semigroups448
  • 4. Semidirect product and wreath product451
  • 5. The wreath product principle458
  • 6. Notes463
  • ANNEX B. VARIETIES OF FINITE SEMIGROUPS465
  • 1. Varieties of algebras465
  • 2. The variety theorem475
  • 3. Some examples of varieties477
  • 4. Star-free sets481
  • 5. Local properties of finite words492
  • 6. Notes498
  • References499
  • List of Tables523
  • List of Figures525
  • Index531
Book details
  • Vendor Elsevier S & T
  • SKU 9780125321112
  • ISBN-13 9780080525648
  • Author Perrin, Dominique; Pin, Jean-Éric
  • Category Computers
  • Subject Computer Science

Do you have questions about this book?

Ask an expert!

Description eBook delivery & access Reviews
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.