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