TLG Texts in Logic and Games
TLG 2 : Logic and Automata

TLG 2 : Logic and Automata

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