Theme of Conference:
The study of the modeltheoretic 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 reconvergence 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 modeltheoretic 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 34hour tutorials, as well as 2hour and 1hour 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:
4HOUR TUTORIALS:

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

Thomas Wilke/ Igor Walukiewicz: Towards understanding tree languages
3HOUR TUTORIALS:

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

Dugald Macpherson/Richard Elwes: Asymptotics of definable sets in finite structures
2HOUR 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
1HOUR TALKS:

Albert Atserias: Random formulas

Manuel Bodirsky: The algebraic approach to infinitevalued 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 ensuite 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