Some results on automatic structures
Hironobu Ishihara, Bakh Khoussainov, Sasha Rubin · 2003
We study the class of countable structures which can be presented by synchronous finite automata. We reduce the problem of existence of an automatic presentation of a structure to that for a graph. We exhibit a series of properties of automatic equivalence structures, linearly ordered sets and permutation structures. These serve as a first step in producing practical descriptions of some automatic structures or illuminating the complexity of doing so for others.