Simple Classes of Automatic Structures

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.