Automata, Logics, and Infinite Games 2001: Dagstuhl, Germany

Erich Grädel, Wolfgang Thomas, Thomas Wilke (Eds.): Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001]. Lecture Notes in Computer Science 2500 Springer 2002, ISBN 3-540-00388-6

Part I. Introduction

Berndt Farwer:
omega-Automata. 3-20
René Mazala:
Infinite Games. 23-42

Part II. Determinization and Complementation

Markus Roggenbach:
Determinization of Büchi-Automata. 43-60
Felix Klaedtke:
Complementation of Büchi Automata Using Alternation. 61-78
Stefan Schwoon:
Determinization and Complementation of Streett Automata. 79-91

Part III. Parity Games

Ralf Küsters:
Memoryless Determinacy of Parity Games. 95-106
Hartmut Klauck:
Algorithms for Parity Games. 107-129

Part IV. Tree Automata

Frank Nießner:
Nondeterministic Tree Automata. 135-152
Daniel Kirsten:
Alternating Tree Automata and Parity Games. 153-167

Part V. Modal µ-Calculus

Júlia Zappe:
Modal µ-Calculus and Alternating Tree Automata. 171-184
Luca Alberucci:
Strictness of the Modal µ-Calculus Hierarchy. 185-201

Part VI. Monadic Second-Order Logic

Mark Weyer:
Decidability of S1S and S2S. 207-230
Klaus Reinhardt:
The Complexity of Translating Logic to Finite Automata. 231-238
Philipp Rohde:
Expressive Power of Monadic Second-Order Logic and Modal µ-Calculus. 239-257

Part VII. Tree-like Models

Martin Leucker:
Prefix-Recognizable Graphs and Monadic Logic. 263-284
Dietmar Berwanger, Achim Blumensath:
The Monadic Theory of Tree-like Structures. 285-302
Thierry Cachat:
Two-Way Tree Automata Solving Pushdown Games. 303-317

Part VIII. Guarded Logics

Thoralf Räsch:
Introduction to Guarded Logics. 321-342
Dietmar Berwanger, Achim Blumensath:
Automata for Guarded Fixed Point Logics. 343-355

Part IX. Appendices

Carsten Fritz:
Some Fixed Point Basics. 359-364

Last update Tue May 22 04:50:51 2012 CET by the DBLP Team —

This material is Open Data

Data released under the ODC-BY 1.0 license — See also our legal information page