form for participation
Main organizer: Iain
Scientific Committee: Michaël
Benedikt (Bell-Labs), Javier Esparza (Stuttgart),
Bradd Hart (McMaster), Christian Michaux (Mons-Hainaut), Charles
Steinhorn (Vassar), Katrin Tent (Bielefeld).
Themes: The study of the model-theoretic properties of
finite structures emerged initially as a branch of classical model
theory. However, in the late 1980s research concerning logics on
finite structures diverged from work in classical model theory. The
consideration of finite structures became intimately related with,
for example, computational and descriptive complexity, model
checking, database theory, verification, etc., so much so that the
boundaries between these subjects are often hard to distinguish.
The methods employed in classical model theory (with its focus
on infinite structures) and finite model theory also grew apart
during this period. Probabilistic techniques, as well as machine
simulations and reductions, play a prominent role in the study of
finite structures, and stand in contrast to the geometric, algebraic,
and analytic methods that pervade classical (infinite) model theory.
Although both classical and finite model theory deal with restricted
classes of structures, the conditions by which such classes are
delimited also have been quite different. Finite model theory
typically concentrates on classes for which particular computing
formalisms, e.g., finite state automata or other restricted models
of computation, can be used to normalize formulas, or for which
decomposition methods from finite graph theory can be applied. In
contrast, infinitary model theory usually places restrictions on
combinatorial or geometric properties of the definable sets of a structure.
Yet, during the last five years or so there have been
indications of a re-convergence of classical model theory and
logical, finite aspects of computer science. This has resulted both
from the interest of computer scientists in new computing and
specification models that make use of infinitary structures, and from
the development of powerful model-theoretic techniques that can
provide insight into finite structures. Although many common themes
have emerged and begun to gain attention, there is significant
potential for wider interaction.
The goal of the workshop on finite and algorithmic model
theory is to explore both emerging and potential connections between
these two areas in greater depth. The workshop will consist of
several 3-4-hour tutorials, as well as 2-hour and 1-hour research
expositions. This format is designed to introduce researchers and
graduate students in the two areas to those topics that are of
fundamental interest and importance, to survey current research, and
to discuss major unsolved problems and directions for future research.
Marko Djordjevic : Connections between Finite and Infinite Model Theory
Kousha Etessami : Analysis of Recursive Markov Chains, Recursive
Markov Decision Processes, and Recursive Stochastic Games
Erich Graedel : Automatic Structures I / Sasha Rubin : Automatic
Stefan Kreutzer/ Nicole Schweikardt : (Finite) Model Theory of Trees
and Tree-like Structures
1-HOUR TALKS :
Location: The workshop will be held at the University
of Durham, UK.
Accomodation be provided at Collingwood
College. The cost of full board from dinner on Sunday 8 January
to lunch on Friday 13 January is £ 400 for en-suite
accommodation. Additional nights or other arrangement can be
requested from the local organizer.
Registration and further information: Participants are asked
to register before September 15, 2005. Details of how to
register and of available funding can be found here.
Please note that in the application form the button
"Registration only" is intended for participants who will
ararnge by themselves accomodation (including meals).
Other inquiries about the Workshop should be addressed to the local