Simple Classes of Automatic Structures

2025/05/28 by Blumensath, Achim
#FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2505.22821

Abstract

We study two subclasses of the class of automatic structures: automatic structures of polynomial growth and Presburger structures. We present algebraic characterisations of the groups and the equivalence structures in these two classes.

Citations

• The additive group of the rationals does not have an automatic presentation

Related

• Three Lectures on Automatic Structures
• The Isomorphism Problem On Classes of Automatic Structures
• Automatic groups associated with word orders other than shortlex
• Automatic structures and boundaries for graphs of groups
• Structures with not too fast unlabelled growth