An Isaac Newton Institute Satellite Workshop - University of Durham

Finite and Algorithmic Model Theory

9 - 13 January 2006

Organiser: Professor Iain Stewart (Durham)

Scientific Committee: Michaël Benedikt (Bell-Labs), Javier Esparza (Stuttgart), Bradd Hart (McMaster), Christian Michaux (Mons-Hainaut), Charles Steinhorn (Vassar), Katrin Tent (Bielefeld).

in association with the Newton Institute programme entitled Logic and Algorithms

Programme | Participants

Theme of Conference:

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.

Invited Speakers:

  4-HOUR TUTORIALS:

  • Martin Otto: Model theory with special classes of (finite) relational structures

  • Thomas Wilke/ Igor Walukiewicz: Towards understanding tree languages

  3-HOUR TUTORIALS:

  • Bart Kuijpers/Jan van den Bussche: Logical Aspects of Spatial Databases

  • Dugald Macpherson/Richard Elwes: Asymptotics of definable sets in finite structures

  2-HOUR TUTORIALS:

  • Marko Djordjevic: Connections between Finite and Infinite Model Theory

  • Kousha Etessami : Analysis of Recursive Markov Chains, Recursive Markov Decision Proceses, and Recursive Stochastic Games

  • Erich Graedel : Automatic Structures I / Sasha Rubin : Automatic Structures II

  • Stefan Kreutzer/ Nicole Schweikardt

  1-HOUR TALKS:

  • Albert Atserias: Random formulas

  • Manuel Bodirsky: The algebraic approach to infinite-valued constraint satisfaction

Location and Cost:

The workshop will take place at the University of Durham and accommodation can be provided at Collingwood College . The conference package, costing £400, includes accommodation in en-suite rooms, breakfast, lunch, dinner, from dinner on Sunday 8 January 2006 to lunch on Friday 13 January 2006. Participants who wish to arrange additional nights or attend but do not require the conference package are very welcome. Further information can be obtained from the local organiser.

Applications Forms:

Are available here. Invited participants to the semester long programme are asked to also apply.

Closing Date:

The closing date for the receipt of applications is 15 September 2005

Additional Information:

Is available here.


Logic and Algorithms | Workshops | Newton Institute Home Page