Ebook: Logic and Automata. History and Perspectives

Издательство Amsterdam University Press, 2008, -737 pp.Mathematical logic and automata theory are two scientific disciplines with a close relationship that is not only fundamental for many theoretical results but also forms the basis of a coherent methodology for the verification and synthesis of computing systems. Although both automata theory and mathematical logic look back to a much longer history, they have come together in the 1960s through the fundamental work of Büchi, Elgot, Rabin and others who showed the expressive equivalence of automata with logical systems such as monadic second-order logic on finite and infinite words and trees. This allowed the handling of specifications (where global system properties are stated) and implementations (which involve the definition of the local steps in order to satisfy the global goals laid out in the specification) in a single framework. Moreover this framework offered algorithmic procedures for essential questions such as the consistency of the specifications or the correctness of implementations. Through the methodology of model-checking the connection between automata theory and logic has indeed become the basis of efficient verification methods with industrial scale applications.
Wolfgang Thomas is one of the leading scientists in logic and automata theory. He has shaped this scientific area, not only through many deep and beautiful results, but also through his ability to bring together different research threads, to provide a convincing synthesis of them, and to point out new and promising directions. For a whole generation of scientists in the field, including most of the collaborators of this volume, his tutorials and surveys on automata theory, language theory and logic, his activities as a teacher, and his lucid contributions at conferences and in informal discussions, have been extremely influential. We now take the occasion of the 60th birthday of Wolfgang Thomas to present a tour d’horizon on automata theory and logic. The twenty papers assembled in this volume, written by experts of the respective area upon invitation by the editors, cover many different facets of logic and automata theory. They emphasize the connections of automata theory and logic to other disciplines such as complexity theory, games, algorithms, and semigroup theory and stress their importance for modern applications in computer science such as the synthesis and verification of reactive systems. The volume puts modern scientific developments into a historical perspective, and shows how they are rooted in more than forty years of automata theory and mathematical logic. Perhaps even more importantly, the authors present and discuss current perspectives of automata and logic based methodologies in different areas of computer science.On the topological complexity of tree languages
Nondeterministic controllers of nondeterministic processes
Reachability in continuous-time Markov reward decision processes
Logical theories and compatible operations
Forest algebras
Automata and semigroups recognizing infinite words
Deterministic graph grammars
Quantifier-free definable graph operations preserving recognizability
First-order definable languages
Matrix-based complexity functions and recognizable picture languages
Applying Blackwell optimality: priority mean-payoff games as limits of multi-discounted games
Logic, graphs, and algorithms
Non-regular fixed-point logics and games
The universal automaton
Deterministic top-down tree automata: past, present, and future
Expressive power of monadic logics on words, trees, pictures, and graphs
Structured strategies in games on graphs
Counting in trees
Modular quantifiers
Automata: from logics to algorithms