Back

Description

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.

Programme

Monday
11.00 - 11.45	Lauri Hella:	Automata and transitive closure logic
11.45 - 12.30	Clemens Lautemann:	First order logic and regular languages
Tuesday
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
Wednesday
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
Thursday
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
Friday
11.00 - 11.45	Magnus Steinby:	On characterizing families of regular tree languages
11.45 - 12.30	Igor Walukiewicz:	Fixpoint hierarchies and automata

• Abstracts
• Transparencies of some of the talks

Organisers

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