Juhani Karhumäki and Kerkko Luosto
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|
|11.45 - 12.30||Clemens Lautemann:||First order logic and regular languages|
|11.00 - 11.45||Erich Grädel:||Alternating automata, games, and logic I|
|11.45 - 12.30||Dietmar Berwanger:||Alternating automata, games, and logic II|
|11.00 - 11.30||Marcin Mostowski:||Some arithmetical operations on spectra|
|11.30 - 12.00||Konrad Zdanowski:||Representability in finite models|
|12.00 - 12.30||Vesa Halava:||Marked post correspondence problem|
|11.00 - 11.30||N.V. Shilov:||On expressive and model checking power of propositional program logics in finite models|
|11.30 - 12.00||Tero Tulenheimo:||On the existence of a modal logical basis for monadic second-order logic|
|12.00 - 12.30||James Rogers:||wMSO theories of multi-dimensional trees|
|11.00 - 11.45||Magnus Steinby:||On characterizing families of regular tree languages|
|11.45 - 12.30||Igor Walukiewicz:||Fixpoint hierarchies and automata|
Department of Mathematics, Statistics and Philosophy
33014 University of Tampere
Department of Mathematics
University of Turku
Department of Mathematics
P.O. Box 4
00014 University of Helsinki