Deciding the isomorphism problem in classes of unary automatic structures
Liu, JL; Minnes, M
MetadataShow full metadata
We solve the isomorphism problem for certain classes of unary automatic structures: unary automatic equivalence relations, unary automatic linear orders, and unary automatic trees. That is, we provide algorithms which decide whether two given elements of these classes are isomorphic. In doing so, we define new finite representations for these structures which give normal forms.