Mathematical logic and automata theory are two scientific disciplines with a fundamentally close relationship. The authors of Logic and Automata take the occasion of the sixtieth birthday of Wolfgang Thomas to present a tour d’horizon of automata theory and logic. The twenty papers in this volume cover many different facets of logic and automata theory, emphasizing the connections to other disciplines such as games, algorithms, and semigroup theory, as well as discussing current challenges in the field.
Author(s): Jorg Flum, Erich Gradel, Thomas Wilke
Series: Texts in Logic and Games, Volume 2
Publisher: Amsterdam University Press
Year: 2008
Language: English
Pages: 737
Table of Contents......Page 6
Preface......Page 8
1. On the topological complexity of tree languages......Page 10
2. Nonederministic controllers of nondeterministic preocesses......Page 30
3. Reachability in continuous-time Markov reward decision processes......Page 54
4. Logical theories and compatible operations......Page 74
5. Forest algebras......Page 108
6. Automata and semigroups recognizing infinite words......Page 134
7. Deterministic graph grammars......Page 170
8. Quantifier-free definable graph opreations preserving recognizability......Page 252
9. First-order definable languages......Page 262
10. Matrix-based complexity functions and recognizable picture languages......Page 308
11. Apllying Blackwell optimality: priority mean-payoff games as limits of multi-discounted games......Page 332
12. Logic, graphs and algorithms......Page 358
13. Non-regular fixed-points logics and games......Page 424
14. The universal automaton......Page 458
15. Deterministic top-down tree automata: past, present, and future......Page 506
16. Expressive power of monadic logics on words, trees, pictures and graphs......Page 532
17. Structured strategies in games on graphs......Page 554
18. Counting in trees......Page 576
19. Modular quantifiers......Page 614
20. Automata: from logics to algorithms......Page 630
