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.
Lauri Hella
Department of Mathematics, Statistics and Philosophy
33014 University of Tampere
Finland
lauri.hella@uta.fi
Juhani Karhumäki
Department of Mathematics
University of Turku
20014 Turku
Finland
karhumak@cs.utu.fi
Kerkko Luosto
Department of Mathematics
P.O. Box 4
00014 University of Helsinki
Finland
kerkko.luosto@helsinki.fi