Volume 2 : Logic and Automata: History and Perspectives 
Jörg Flum and Erich Grädel and Thomas Wilke (eds.)
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.
We 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 cover many different facets of logic and automata theory, emphasize the connections to other disciplines such as complexity theory, games, algorithms, and semigroup theory, and discuss current challenges in this field.
|
 |
Preface 7–8
André Arnold , Jacques Duparc, Filip Murlak, Damian Niwiński
On the topological complexity of tree languages 9–28
André Arnold , Igor Walukiewicz
Nondeterministic controllers of nondeterministic processes 29–52
Christel Baier , Boudewijn R. Haverkort, Holger Hermanns, Joost-Pieter Katoen
Reachability in continuous-time Markov reward decision processes 53–72
Achim Blumensath, Thomas Colcombet, Christof Löding
Logical theories and compatible operations 73–106
Mikolaj Bojańczyk, Igor Walukiewicz
Forest algebras 107–132
Olivier Carton, Dominique Perrin, Jean-Eric Pin
Automata and semigroups recognizing infinite words 133–168
Didier Caucal
Deterministic graph grammars 169–250
Bruno Courcelle
Quantifier-free definable graph operations preserving recognizability 251–260
Volker Diekert, Paul Gastin
First-order definable languages 261–306
Dora Giammarresi, Antonio Restivo
Matrix-based complexity functions and recognizable picture languages 307–330
Hugo Gimbert, Wieslaw Zielonka
Applying Blackwell optimality: priority mean-payoff games as limits of multi-discounted games 331–356
Martin Grohe
Logic, graphs, and algorithms 357–422
Stephan Kreutzer, Martin Lange
Non-regular fixed-point logics and games 423–456
Sylvain Lombardy, Jacques Sakarovitch
The universal automaton 457–504
Wim Martens, Frank Neven, Thomas Schwentick
Deterministic top-down tree automata: past, present, and future 505–530
Oliver Matz, Nicole Schweikardt
Expressive power of monadic logics on words, trees, pictures, and graphs 531–552
R. Ramanujam, Sunil Simon
Structured strategies in games on graphs 553–574
Bruno Courcelle
Counting in trees 575–612
Howard Straubing, Denis Thérien
Modular quantifiers 613–628
Moshe Y. Vardi, Thomas Wilke
Automata: from logics to algorithms 629–736
