Axiomatising Tree-interpretable Structures

Achim Blumensath

We introduce the class of tree-interpretable structures which generalises
the notion of a prefix-recognisable graph to arbitrary relational
structures. We prove that every tree-interpretable structure is finitely
axiomatisable in guarded second-order logic with cardinality quantifiers.