Deciding the isomorphism problem in classes of unary automatic structures (Q2430013)

The authors consider the isomorphism problem for unary automatic structures, i.e., for automatic structures defined by finite automata over a one-element alphabet. They prove that this problem is decidable for the classes of unary automatic equivalences and unary automatic linear orders in linear time in the sizes of the input automata defining these structures. A characterization of unary automatic trees is given, and the isomorphism problem for automatic trees is proven to be decidable in time polynomial in the number of states of the representing automata.