Automata and Finite Model Theory

Lauri Hella, Juhani Karhumäki and Kerkko Luosto
Section: Computation
Level: Workshop


Finite model theory can be succinctly described as the study of expressive power of logical languages on classes of finite structures. Since inputs to all usual computational problems can be viewed as finite models, logics can be used to obtain a new measure of complexity: the complexity of logical descriptions of problems. This is the key idea of a branch of finite model theory, known as descriptive complexity theory.

The main results in this area are logical characterizations of complexity classes. Historically the first logical characterization of this type was proved by Büchi (1960), who showed that a language is regular if and only if it is definable in monadic second order logic. On the other hand, a language is regular if and only if it is recognized by a finite automaton. Thus, Büchi's theorem reveals an interesting connection between Finite model theory and Automata theory.

The recent years have witnessed a revitalized interest in the connections between these two fields. In particular, Automata theory provides powerful methods for solving definability problems on finite models: Thomas and Matz (1997) used growth arguments for proving that the alternation hierarchy of monadic second order logic is strict. Furhtermore, tree automata have been used for proving decidability results for guarded fragments of first order logic and some of its extensions (Grädel 1999).

The aim of this workshop is to bring together researchers from the fields of Automata theory and formal languages, on one hand, and from Finite model theory and descriptive complexity, on the other hand, and to explore connections between these fields.


11.00 - 11.45 Lauri Hella: Automata and transitive closure logic PS PDF
11.45 - 12.30 Clemens Lautemann: First order logic and regular languages PS PDF
11.00 - 11.45 Erich Grädel: Alternating automata, games, and logic I PS PDF
11.45 - 12.30 Dietmar Berwanger: Alternating automata, games, and logic II PS PDF
11.00 - 11.30 Marcin Mostowski: Some arithmetical operations on spectra PS PDF
11.30 - 12.00 Konrad Zdanowski: Representability in finite models PS PDF
12.00 - 12.30 Vesa Halava: Marked post correspondence problem PS PDF
11.00 - 11.30 N.V. Shilov: On expressive and model checking power of propositional program logics in finite models PS PDF
11.30 - 12.00 Tero Tulenheimo: On the existence of a modal logical basis for monadic second-order logic PS PDF
12.00 - 12.30 James Rogers: wMSO theories of multi-dimensional trees PS PDF
11.00 - 11.45 Magnus Steinby: On characterizing families of regular tree languages PS PDF
11.45 - 12.30 Igor Walukiewicz: Fixpoint hierarchies and automata PS PDF


Lauri Hella
Department of Mathematics, Statistics and Philosophy
33014 University of Tampere

Juhani Karhumäki
Department of Mathematics
University of Turku
20014 Turku

Kerkko Luosto
Department of Mathematics
P.O. Box 4
00014 University of Helsinki