Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 


The isomorphism problem on classes of automatic structures with transitive relations

Authors: Dietrich Kuske, Jiamou Liu and Markus Lohrey
Journal: Trans. Amer. Math. Soc. 365 (2013), 5103-5151
MSC (2010): Primary 03D05, 03D45, 03C57
Published electronically: May 20, 2013
MathSciNet review: 3074369
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Automatic structures are finitely presented structures where the universe and all relations can be recognized by finite automata. It is known that the isomorphism problem for automatic structures is complete for $ \Sigma ^1_1$, the first existential level of the analytical hierarchy. Positive results on ordinals and on Boolean algebras raised hope that the isomorphism problem is simpler for transitive relations. We prove that this is not the case. More precisely, this paper shows:

The isomorphism problem for automatic equivalence relations is complete for $ \Pi ^0_1$ (the first universal level of the arithmetical hierarchy).
The isomorphism problem for automatic trees of height $ n \geq 2$ is $ \Pi ^0_{2n-3}$-complete.
The isomorphism problem for well-founded automatic order trees is recursively equivalent to true first-order arithmetic.
The isomorphism problem for automatic order trees is $ \Sigma ^1_1$-complete.
The isomorphism problem for automatic linear orders is $ \Sigma ^1_1$-complete.
We also obtain $ \Pi ^0_1$-completeness of the elementary equivalence problem for several classes of automatic structures and $ \Sigma ^1_1$-completeness of the isomorphism problem for trees (resp., linear orders) consisting of a deterministic context-free language together with the prefix order (resp., lexicographic order). This solves several open questions of Ésik, Khoussainov, Nerode, Rubin, and Stephan.

References [Enhancements On Off] (What's this?)

  • 1. C. J. Ash and J. Knight.
    Computable structures and the hyperarithmetical hierarchy, volume 144 of Studies in Logic and the Foundations of Mathematics.
    North-Holland Publishing Co., Amsterdam, 2000. MR 1767842 (2001k:03090)
  • 2. V. Bárány.
    A hierarchy of automatic omega-words having a decidable MSO theory.
    RAIRO Theor. Inform. Appl., 42(3):417-450, 2008. MR 2434027 (2010d:03057)
  • 3. V. Bárány, L. Kaiser, and S. Rubin.
    Cardinality and counting quantifiers on omega-automatic structures.
    In Proceedings of STACS 2008, pages 385-396. IFIB Schloss Dagstuhl, 2008. MR 2873751
  • 4. S. L. Bloom and Z. Ésik.
    Algebraic linear orderings.
    Internat. J. Found. Comput. Sci., 22(2):491-515, 2011. MR 2772821 (2012e:06001)
  • 5. A. Blumensath and E. Grädel.
    Automatic structures.
    In Proceedings of LICS 2000, pages 51-62. IEEE Computer Society Press, 2000. MR 1946085
  • 6. A. Blumensath and E. Grädel.
    Finite presentations of infinite structures: Automata and interpretations.
    Theory Comput. Syst., 37(6):641-674, 2004. MR 2093606 (2005g:03052)
  • 7. G. Braun and L. Strüngmann.
    Breaking up finite automata presentable torsion-free abelian groups.
    International Journal of Algebra and Computation, 21(8):1463-1472, 2011. MR 2864567
  • 8. W. Calvert, D. Cenzer, V. Harizanov, and A. Morozov.
    Effective categoricity of equivalence structures.
    Ann. Pure Appl. Logic, 141:61-78, 2006. MR 2229930 (2007j:03048)
  • 9. W. Calvert and J. F. Knight.
    Classification from a computable viewpoint.
    Bull. Symbolic Logic, 12(2):191-218, 2006. MR 2223921 (2007b:03067)
  • 10. W. Calvert, J. F. Knight, and J. Millar.
    Computable trees of Scott rank $ \omega ^{CK}_1$, and computable approximation.
    J. Symb. Log., 71(1):283-298, 2006. MR 2210068 (2006j:03057)
  • 11. D. Cenzer and J. B. Remmel.
    Complexity Theoretic Model Theory and Algebra.
    In Y. L. Ershov, S. S. Goncharov, V. Marek, A. Nerode, and J. Remmel, editors, Handbook of Recursive Mathematics, Vol 1,
    pages 381-513.
    Elsevier, 1998. MR 1673574 (2000d:03077)
  • 12. Ch. Delhommé.
    Non-automaticity of $ \omega ^\omega $.
    2001. Manuscript.
  • 13. Ch. Delhommé.
    Automaticité des ordinaux et des graphes homogènes.
    C. R. Acad. Sci. Paris, Ser. I, 339:5-10, 2004. MR 2075224 (2005b:03093)
  • 14. A. Durand-Gasselin and P. Habermehl.
    Ehrenfeucht-Fraïssé goes elementarily automatic for structures of bounded degree.
    In Proceedings of STACS 2011. pages 242-253. IFIB Schloss Dagstuhl, 2011.
  • 15. C. Elgot.
    Decision problems of finite automata design and related arithmetics.
    Trans. Am. Math. Soc., 98:21-51, 1961. MR 0139530 (25:2962)
  • 16. Z. Ésik.
    An undecidable property of context-free linear orders.
    Inform. Process. Lett., 111(3):107-109, 2011. MR 2724596 (2011k:68080)
  • 17. D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson, and W. P. Thurston.
    Word processing in groups.
    Jones and Bartlett, Boston, 1992. MR 1161694 (93i:20036)
  • 18. Y. L. Ershov, S. S. Goncharov, V. W. Marek, A. Nerode, and J. Remmel, eds.
    Handbook of Recursive Mathematics: Volume 1, 2.
    Elsevier, 1998. MR 1673617 (99k:03003); MR 1673582 (99k:03004)
  • 19. S. S. Goncharov and J. F. Knight.
    Computable structure and antistructure theorems (Russian).
    Algebra i Logika, 41(6):639-681, 2002. English translation appeared as: Computable structures and non-structure theorems. Algebra and Logic, 41(6):351-373, 2002. MR 1967769 (2004a:03047)
  • 20. D. R. Hirschfeldt and W. M. White.
    Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures.
    Notre Dame J. Form. Log., 43(1):51-64 (2003), 2002. MR 2033315 (2005d:03084)
  • 21. W. Hodges.
    Model Theory.
    Cambridge University Press, 1993. MR 1221741 (94e:03002)
  • 22. B. R. Hodgson.
    On direct products of automaton decidable theories.
    Theoret. Comput. Sci., 19:331-335, 1982. MR 671875 (83m:03046)
  • 23. J. Honkala.
    On the problem whether the image of an $ \mathbb{N}$-rational series equals $ \mathbb{N}$.
    Fund. Inform., 73(1-2):127-132, 2006. MR 2255552 (2007h:68136)
  • 24. J. E. Hopcroft and J. D. Ullman.
    Introduction to automata theory, languages and computation.
    Addison-Wesley, Reading, MA, 1979. MR 645539 (83j:68002)
  • 25. H. Ishihara, B. Khoussainov, and S. Rubin.
    Some results on automatic structures.
    In Proceedings of LICS 2002, pages 235-244. IEEE Computer Society Press, 2002.
  • 26. A. Kartzow, J. Liu, and M. Lohrey.
    Tree-Automatic well-founded trees.
    To appear in Logical Methods in Computer Science, 2013.
  • 27. B. Khoussainov and M. Minnes.
    Model theoretic complexity of automatic structures.
    In Proceedings of TAMC 2008, number 4978 in Lecture Notes in Computer Science, pages 514-525. Springer, 2008. MR 2472713
  • 28. B. Khoussainov and A. Nerode.
    Automatic presentations of structures.
    In LCC: International Workshop on Logic and Computational Complexity, number 960 in Lecture Notes in Computer Science, pages 367-392, 1995. MR 1449670
  • 29. B. Khoussainov and A. Nerode.
    Open questions in the theory of automatic structures.
    Bulletin of the EATCS, 94, pages 181-204, 2008. MR 2410292 (2009c:03033)
  • 30. B. Khoussainov, A. Nies, S. Rubin, and F. Stephan.
    Automatic structures: Richness and limitations.
    Log. Methods Comput. Sci., 3(2):2:2, 18 pp. (electronic), 2007. MR 2306568 (2008a:03064)
  • 31. B. Khoussainov, S. Rubin, and F. Stephan.
    Automatic linear orders and trees.
    ACM Trans. Comput. Log., 6(4):675-700, 2005. MR 2176784 (2007c:03052)
  • 32. D. Kuske.
    Where automatic structures benefit from weighted automata.
    In Bozapalidis Festschrift, number 7020 in Lecture Notes in Computer Science, pages 257-271. Springer, 2011.
  • 33. D. Kuske.
    Isomorphisms of scattered automatic linear orders.
    In Proc. of CSL '12, Leibniz International Proceedings in Informatics (LIPIcs) vol. 16, pages 455-469. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2012.
  • 34. D. Kuske, J. Liu, and M. Lohrey.
    The isomorphism problem for $ \omega $-automatic trees.
    In Proceedings of CSL 2009, number 6247 in Lecture Notes in Computer Science, pages 396-410. Springer, 2010. MR 2755316 (2012d:03079)
  • 35. D. Kuske and M. Lohrey.
    Some natural decision problems in automatic graphs.
    J. Symbolic Logic, 75(2):678-710, 2010. MR 2648160 (2011j:03094)
  • 36. D. Kuske and M. Lohrey.
    Automatic structures of bounded degree revisited.
    Journal of Symbolic Logic, 76(4):1352-1380, 2011. MR 2895400
  • 37. M. Lohrey and C. Mathissen.
    Isomorphism of regular trees and words.
    In Proceedings of ICALP 2011, number 6756 in Lecture Notes in Computer Science, pages 210-221. Springer, 2011. MR 2852427
  • 38. J. Liu and M. Minnes.
    Analysing Complexity in Classes of Unary Automatic Structures.
    In Proceedings of LATA 2009, number 5457 in Lecture Notes in Computer Science, pages 514-525. Springer, 2009. MR 2544442
  • 39. Y. V. Matiyasevich.
    Hilbert's Tenth Problem.
    MIT Press, Cambridge, Massachusetts, 1993. MR 1244324 (94m:03002b)
  • 40. A. Nies.
    Describing groups.
    Bull. Symbolic Logic, 13(3):305-339, 2007. MR 2359909 (2008j:20001)
  • 41. H. Rogers.
    Theory of Recursive Functions and Effective Computability.
    McGraw-Hill, 1968. MR 0224462 (37:61)
  • 42. J. Rosenstein.
    Linear Ordering.
    Academic Press, 1982. MR 662564 (84m:06001)
  • 43. S. Rubin.
    Automatic Structures.
    PhD thesis, University of Auckland, 2004.
  • 44. S. Rubin.
    Automata presenting structures: A survey of the finite string case.
    Bull. Symbolic Logic, 14:169-209, 2008. MR 2413002 (2009d:03094)
  • 45. A. Salomaa and M. Soittola.
    Automata-theoretic aspects of formal power series.
    Springer, 1978. MR 0483721 (58:3698)
  • 46. R. I. Soare.
    Recursively enumerable sets and degrees.
    Perspectives in Mathematical Logic. Springer, 1987. MR 882921 (88m:03003)
  • 47. W. Thomas.
    On frontiers of regular trees.
    RAIRO Theor. Inform. Appl., 20:371-381, 1986. MR 880841 (89c:68065)
  • 48. T. Tsankov.
    The additive group of the rationals does not have an automatic presentation.
    J. Symbolic Logic, 76(4):1341-1351, 2011. MR 2895399
  • 49. A. Weber.
    On the valuedness of finite transducers.
    Acta Informat., 27:749-780, 1990. MR 1080581 (91i:68024)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03D05, 03D45, 03C57

Retrieve articles in all journals with MSC (2010): 03D05, 03D45, 03C57

Additional Information

Dietrich Kuske
Affiliation: Institut für Theoretische Informatik, TU Ilmenau, Postfach 100565, D-98684 Ilmenau, Germany

Jiamou Liu
Affiliation: Department of Computer Science, University of Aukland, Private Bag 92019, Auckland, New Zealand

Markus Lohrey
Affiliation: Institut für Informatik, Universität Leipzig, Augustusplatz 10-11, D-04109 Leipzig, Germany

Keywords: Recursion-theoretic complexity, automatic structures, natural problems in the arithmetical hierarchy
Received by editor(s): September 24, 2011
Received by editor(s) in revised form: December 1, 2011
Published electronically: May 20, 2013
Additional Notes: The second and third authors were supported by the DFG research project GELO
Article copyright: © Copyright 2013 American Mathematical Society

American Mathematical Society