##### Dagstuhl Seminar 07441

### Algorithmic-Logical Theory of Infinite Structures

##### ( Oct 28 – Nov 02, 2007 )

##### Permalink

##### Organizers

- Rodney Downey (Victoria University of Wellington, NZ)
- Bakh Khoussainov (University of Auckland, NZ)
- Dietrich Kuske (Universität Leipzig, DE)
- Markus Lohrey (Universität Leipzig, DE)
- Moshe Y. Vardi (Rice University - Houston, US)

##### Contact

- Simone Schilke (for administrative matters)

One of the important research fields of theoretical and applied computer science and mathematics is the study of algorithmic, logical and model theoretic properties of structures and their interactions. By a structure we mean typical objects that arise in computer science and mathematics such as data structures, programs, transition systems, graphs, large databases, XML documents, algebraic systems including groups, integers, fields, Boolean algebras and so on.

From a mathematics point of view these are natural objects of study and the theory of computable structures initiated by Malcev and Rabin in the 60s witnesses it. This mathematical study has been one of the most active areas of research in the last decade. {}From a computer science point of view, there has been a growing interest in understanding infinite structures. The need for this study comes from the fact that one cannot usually put bounds on typical objects of computer science such as the sizes of databases, programs, XML documents, stacks, communication buffers, and so on. Moreover, these objects are usually not seen as static components but are modified in a dynamic way, which leads to systems with infinite state spaces, i.e., infinite transition systems. These transition systems can be modeled by infinite graphs, where nodes correspond to states of the system and edges correspond to transitions between the states. Properties of such systems can be expressed in logical formalisms and it is an algorithmic task to determine the validity of such formulas or to calculate the set of states satisfying a certain property. In computer science, the following aspects for a logical theory of such systems are of interest.

- Infinite systems in computer science are usually represented by some finite description or abstract machine; system states are then configurations of that abstract machine.
- These system states have some internal structure that determines the global properties of the system. E.g., they may be represented by natural numbers, finite strings, trees, or graphs and transitions are defined by transducers on the data structures.
- The emphasis is put on efficient algorithms for the verification of system properties that are specified in a suitable logical language.

Several aspects of such a unified theory have already been addressed in the past. These include:

- Computable model theory, a branch of classical model theory and recursion theory, considers structures that are presented in some effective (and thus finite) way. An emphasis in this field is to study algorithmic properties of structures by comparing complexities of their undecidable features. Typical important structures in this context such as arithmetic of natural numbers do not have decidable first order theories. Essential tools of research here are the Turing degrees and methods of recursion theory.
- The theory of automatic structures, a newly formed direction of research in which structures are represented by finite state machines such as finite automata, tree automata, $\omega$-automata, etc. In contrast to computable model theory, an emphasis here is given to understanding the algorithmic properties of structures by comparing complexities of their decidable features. All these structures have decidable first order theories. The development of this theory is based on methods of complexity theory, finite combinatorics, model theory and automata theory.
- Classes of infinite graphs that are generated by some kind of abstract machines and that lead to decidable monadic second-order theories became an active research topic in recent years. Currently, the most general class of graphs with decidable monadic second-order theories is the Caucal hierarchy. Graphs that are generated by ground tree rewriting systems constitute a class, were monadic second-order logic is undecidable in general, but first-order logic with reachability is still decidable.
- Several approaches for model-checking systems with infinite state spaces were developed in the past by researchers working in verification. Typical examples in this context are unbounded communication buffers, stacks in procedural programming languages, or parameterized systems.

At this seminar, researchers from all these fields met. To give the non-specialists a general overview of the flavor, topics, methods, and open questions of the other fields, we had five keynotes given by Igor Walukiewicz, Wolfgang Thomas, Denis Hirschfeldt, Sasha Rubin, and Parosh Aziz Abdulla. These were complemented by contributed talks of the participants that span the whole spectrum laied out above.

- Parosh Aziz Abdulla (Uppsala University, SE) [dblp]
- Vince Bárány (RWTH Aachen, DE)
- Dietmar Berwanger (RWTH Aachen, DE) [dblp]
- Achim Blumensath (TU Darmstadt, DE) [dblp]
- Julian Bradfield (University of Edinburgh, GB) [dblp]
- Thierry Cachat (University Paris-Diderot, FR)
- Arnaud Carayol (INRIA Rennes - Bretagne Atlantique, FR) [dblp]
- Olivier Carton (University Paris-Diderot, FR) [dblp]
- Didier Caucal (Université Paris-Est, FR)
- Thomas Colcombet (University Paris-Diderot, FR) [dblp]
- Christian Delhommé (Université de la Réunion - Saint Denis, FR)
- Volker Diekert (Universität Stuttgart, DE) [dblp]
- Rodney Downey (Victoria University of Wellington, NZ) [dblp]
- Manfred Droste (Universität Leipzig, DE) [dblp]
- Stefan Göller (Universität Leipzig, DE) [dblp]
- Denis R. Hirschfeldt (University of Chicago, US) [dblp]
- Petr Jancar (TU - Ostrava, CZ) [dblp]
- Lukasz Kaiser (RWTH Aachen, DE) [dblp]
- Bakh Khoussainov (University of Auckland, NZ) [dblp]
- Felix Klaedtke (ETH Zürich, CH) [dblp]
- Antonin Kucera (Masaryk University - Brno, CZ) [dblp]
- Dietrich Kuske (Universität Leipzig, DE) [dblp]
- Steffen Lempp (University of Wisconsin - Madison, US) [dblp]
- Christof Löding (RWTH Aachen, DE) [dblp]
- Markus Lohrey (Universität Leipzig, DE) [dblp]
- Denis Lugiez (University of Marseille, FR)
- Richard Mayr (North Carolina State University - Raleigh, US) [dblp]
- Mia Minnes (Cornell University, US)
- Andrey Morozov (Sobolev Institute of Mathematics - Novosibirsk, RU)
- Anca Muscholl (University of Bordeaux, FR) [dblp]
- André Otfrid Nies (University of Auckland, NZ) [dblp]
- Damian Niwinski (University of Warsaw, PL) [dblp]
- Chih-Hao Luke Ong (University of Oxford, GB) [dblp]
- Alexander Rabinovich (Tel Aviv University, IL) [dblp]
- Sasha Rubin (University of Auckland, NZ) [dblp]
- Philippe Schnoebelen (ENS - Cachan, FR) [dblp]
- Thomas Schwentick (TU Dortmund, DE) [dblp]
- Stefan Schwoon (TU München, DE)
- Luc Segoufin (University of Paris South XI, FR) [dblp]
- Olivier Serre (University Paris-Diderot, FR)
- Richard A. Shore (Cornell University, US) [dblp]
- Jiri Srba (Aalborg University, DK) [dblp]
- Colin Stirling (University of Edinburgh, GB)
- Rick Thomas (University of Leicester, GB)
- Wolfgang Thomas (RWTH Aachen, DE) [dblp]
- Igor Walukiewicz (University of Bordeaux, FR) [dblp]

##### Classification

- Logic
- complexity

##### Keywords

- theories of infinite structures
- computable model theory and automatic structures
- model checking infinite systems