TU Darmstadt Mathematik Fachgebiete Logic group Research Algorithmic Model Theory Finitely Representable Structures

The study of algorithmic properties of infinite structures crucially relies on methods of finite presentations of such structures and on structural operations in terms of these presentations. Central questions regarding a given encoding are:

- which structures have a representation of this kind?
- which operations on such representations are computable?

Frequently, the algorithmic properties of a given type of representation can be determined easily. But characterising those structures that possess such a representation is usually highly non-trivial. So far, we have investigated the following classes of finitely presented structures:

- automatic structures [B99, BG00, BG02, BG04];
- tree-interpretable structures [B04];
- the Caucal hierarchy [B08];
- configuration graphs of various kinds of pushdown automata [K09,K10, K10b] (follow this link).

The focus is on methods to show that a given structure does not belong to

the class under consideration.

[B99] Achim Blumensath, *Automatic Structures*, Diploma Thesis, RWTH Aachen, 1999

[BG00] Achim Blumensath, Erich Grädel Automatic Structures, *Proc. 15th IEEE Symp. on Logic in Computer Science*, 2000, pp. 51-62

[BG02] Achim Blumensath and Erich Grädel, Finite Presentations of Infinite Structures: Automata and Interpretations, *Proc. 2nd Int. Workshop on Complexity in Automated Deduction, CiAD 2002*

[BG04] Achim Blumensath and Erich Grädel, Finite Presentations of Infinite Structures: Automata and Interpretations, *Theory of Computing Systems*, 37(2004), pp. 641-674, **(C) Springer-Verlag**

[B02] Achim Blumensath, Axiomatising tree-interpretable structures, *Proc. 19th Int. Symp. on Theoretical Aspects of Computer Science*, LNCS 2285(2002), pp. 596-607, **(C) Springer-Verlag**

[B04] Achim Blumensath, Axiomatising tree-interpretable structures, *Theory of Computing Systems*, 37(2004), pp. 3-27, **(C) Springer-Verlag**

[B08] Achim Blumensath, On the structure of graphs in the Caucal hierarchy, *Theoretical Computer Science,* 400(2008), pp. 19-45