Axiomatising tree-interpretable structures (Q705058)

This paper is a new contribution to the study of the algorithmic properties of infinite structures. The topic is motivated by several problems in various areas of computer science. The author extends the notion of a prefix-recognizable graph to general relational structures by introducing tree-interpretable structures. The main result is that any tree-interpretable structure is finitely axiomatizable in guarded second-order logic with cardinality quantifiers, but also several other results are obtained. Moreover, the author poses some open problems.