Analysing Complexity in Classes of Unary Automatic Structures

摘要

This paper addresses the time complexity of several queries (including membership and isomorphism) in classes of unary automatic structures and the state complexity of describing these classes. We focus on unary automatic equivalence relations, linear orders, trees, and graphs with finite degree. We prove that in various senses, the complexity of these classes is low: (1) For the isomorphism problem, we either greatly improve known algorithms (reducing highly exponential bounds to small polynomials) or answer open questions about the existence of a decision procedure; (2) for state complexity, we provide polynomial bounds with respect to natural measures of the sizes of the structures.