Infinite Words: Automata, Semigroups, Logic and Games
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.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Chapter VIII AN EXCURSION INTO LOGIC
Other editions - View all
alphabet aperiodic automata automaton recognizing boolean combination Borel sets Büchi automaton chain closed combination of subsets complement conditions are equivalent congruence Corollary countable defined definition denote elements Example Exercise exists factor finite number finite semigroup finite union following conditions formula function hence hierarchy idempotent implies induction infinite trees infinite words integer label Lemma length linked pair locally testable logic metric space monoid morphism Muller automaton node nonempty open sets order ideal ordered semigroup parity automaton Player positive boolean prefix Proposition prove quotient Rabin automaton recognizable sets recognizable subset resp result satisfies the identity second-order logic semigroup morphism sequence set of infinite shows star-free star-free sets subset of A+ successful path suffices superchain surjective surjective morphism Suslin sets syntactic topology transformation semigroup transition tree automaton union of subsets weakly recognized winning strategy X-chain