The isomorphism problem on classes of automatic structures with transitive relations

Kuske, Dietrich; Liu, Jiamou; Lohrey, Markus

doi:10.1090/S0002-9947-2013-05766-2

The isomorphism problem on classes of automatic structures with transitive relations
HTML articles powered by AMS MathViewer

by Dietrich Kuske, Jiamou Liu and Markus Lohrey PDF

Trans. Amer. Math. Soc. 365 (2013), 5103-5151 Request permission

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

C. J. Ash and J. Knight, Computable structures and the hyperarithmetical hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland Publishing Co., Amsterdam, 2000. MR 1767842
Vince Bárány, A hierarchy of automatic $\omega$-words having a decidable MSO theory, Theor. Inform. Appl. 42 (2008), no. 3, 417–450. MR 2434027, DOI 10.1051/ita:2008008
Łukasz Kaiser, Sasha Rubin, and Vince Bárány, Cardinality and counting quantifiers on omega-automatic structures, STACS 2008: 25th International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 1, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2008, pp. 385–396. MR 2873751
S. L. Bloom and Z. Ésik, Algebraic linear orderings, Internat. J. Found. Comput. Sci. 22 (2011), no. 2, 491–515. MR 2772821, DOI 10.1142/S0129054111008155
Achim Blumensath and Erich Grädel, Automatic structures, 15th Annual IEEE Symposium on Logic in Computer Science (Santa Barbara, CA, 2000) IEEE Comput. Soc. Press, Los Alamitos, CA, 2000, pp. 51–62. MR 1946085, DOI 10.1109/LICS.2000.855755
Achim Blumensath and Erich Grädel, Finite presentations of infinite structures: automata and interpretations, Theory Comput. Syst. 37 (2004), no. 6, 641–674. MR 2093606, DOI 10.1007/s00224-004-1133-y
Gábor Braun and Lutz Strüngmann, Breaking up finite automata presentable torsion-free abelian groups, Internat. J. Algebra Comput. 21 (2011), no. 8, 1463–1472. MR 2864567, DOI 10.1142/S0218196711006625
Wesley Calvert, Douglas Cenzer, Valentina Harizanov, and Andrei Morozov, Effective categoricity of equivalence structures, Ann. Pure Appl. Logic 141 (2006), no. 1-2, 61–78. MR 2229930, DOI 10.1016/j.apal.2005.10.002
Wesley Calvert and Julia F. Knight, Classification from a computable viewpoint, Bull. Symbolic Logic 12 (2006), no. 2, 191–218. MR 2223921
Wesley Calvert, Julia F. Knight, and Jessica Millar, Computable trees of Scott rank $\omega _1^{CK}$, and computable approximation, J. Symbolic Logic 71 (2006), no. 1, 283–298. MR 2210068, DOI 10.2178/jsl/1140641175
D. Cenzer and J. B. Remmel, Complexity-theoretic model theory and algebra, Handbook of recursive mathematics, Vol. 1, Stud. Logic Found. Math., vol. 138, North-Holland, Amsterdam, 1998, pp. 381–513. MR 1673574, DOI 10.1016/S0049-237X(98)80011-6
Ch. Delhommé. Non-automaticity of $\omega ^\omega$. 2001. Manuscript.
Christian Delhommé, Automaticité des ordinaux et des graphes homogènes, C. R. Math. Acad. Sci. Paris 339 (2004), no. 1, 5–10 (French, with English and French summaries). MR 2075224, DOI 10.1016/j.crma.2004.03.035
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.
Calvin C. Elgot, Decision problems of finite automata design and related arithmetics, Trans. Amer. Math. Soc. 98 (1961), 21–51. MR 139530, DOI 10.1090/S0002-9947-1961-0139530-9
Z. Ésik, An undecidable property of context-tree linear orders, Inform. Process. Lett. 111 (2011), no. 3, 107–109. MR 2724596, DOI 10.1016/j.ipl.2010.10.018
David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvio V. F. Levy, Michael S. Paterson, and William P. Thurston, Word processing in groups, Jones and Bartlett Publishers, Boston, MA, 1992. MR 1161694
Yu. L. Ershov, S. S. Goncharov, A. Nerode, J. B. Remmel, and V. W. Marek (eds.), Handbook of recursive mathematics. Vol. 1, Studies in Logic and the Foundations of Mathematics, vol. 138, North-Holland, Amsterdam, 1998. Recursive model theory. MR 1673617
S. S. Goncharov and Dzh. Naĭt, Computable structure and antistructure theorems, Algebra Logika 41 (2002), no. 6, 639–681, 757 (Russian, with Russian summary); English transl., Algebra Logic 41 (2002), no. 6, 351–373. MR 1967769, DOI 10.1023/A:1021758312697
Denis R. Hirschfeldt and Walker M. White, Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures, Notre Dame J. Formal Logic 43 (2002), no. 1, 51–64 (2003). MR 2033315, DOI 10.1305/ndjfl/1071505769
Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741, DOI 10.1017/CBO9780511551574
Bernard R. Hodgson, On direct products of automaton decidable theories, Theoret. Comput. Sci. 19 (1982), no. 3, 331–335. MR 671875, DOI 10.1016/0304-3975(82)90042-1
Juha Honkala, On the problem whether the image of an $N$-rational series equals $N$, Fund. Inform. 73 (2006), no. 1-2, 127–132. MR 2255552
John E. Hopcroft and Jeffrey D. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley Series in Computer Science, Addison-Wesley Publishing Co., Reading, Mass., 1979. MR 645539
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.
A. Kartzow, J. Liu, and M. Lohrey. Tree-Automatic well-founded trees. To appear in Logical Methods in Computer Science, 2013.
Bakhadyr Khoussainov and Mia Minnes, Model theoretic complexity of automatic structures (extended abstract), Theory and applications of models of computation, Lecture Notes in Comput. Sci., vol. 4978, Springer, Berlin, 2008, pp. 514–525. MR 2472713, DOI 10.1007/978-3-540-79228-4_{4}5
Bakhadyr Khoussainov and Anil Nerode, Automatic presentations of structures, Logic and computational complexity (Indianapolis, IN, 1994) Lecture Notes in Comput. Sci., vol. 960, Springer, Berlin, 1995, pp. 367–392. MR 1449670, DOI 10.1007/3-540-60178-3_{9}3
Bakhadyr Khoussainov and Anil Nerode, Open questions in the theory of automatic structures, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 94 (2008), 181–204. MR 2410292
Bakhadyr Khoussainov, André Nies, Sasha Rubin, and Frank Stephan, Automatic structures: richness and limitations, Log. Methods Comput. Sci. 3 (2007), no. 2, 2:2, 18. MR 2306568, DOI 10.2168/LMCS-3(2:2)2007
Bakhadyr Khoussainov, Sasha Rubin, and Frank Stephan, Automatic linear orders and trees, ACM Trans. Comput. Log. 6 (2005), no. 4, 675–700. MR 2176784, DOI 10.1145/1094622.1094625
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.
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.
Dietrich Kuske, Jiamou Liu, and Markus Lohrey, The isomorphism problem for $\omega$-automatic trees, Computer science logic, Lecture Notes in Comput. Sci., vol. 6247, Springer, Berlin, 2010, pp. 396–410. MR 2755316, DOI 10.1007/978-3-642-15205-4_{3}1
Dietrich Kuske and Markus Lohrey, Some natural decision problems in automatic graphs, J. Symbolic Logic 75 (2010), no. 2, 678–710. MR 2648160, DOI 10.2178/jsl/1268917499
Dietrich Kuske and Markus Lohrey, Automatic structures of bounded degree revisited, J. Symbolic Logic 76 (2011), no. 4, 1352–1380. MR 2895400
Markus Lohrey and Christian Mathissen, Isomorphism of regular trees and words, Automata, languages and programming. Part II, Lecture Notes in Comput. Sci., vol. 6756, Springer, Heidelberg, 2011, pp. 210–221. MR 2852427, DOI 10.1007/978-3-642-22012-8_{1}6
Jiamou Liu and Mia Minnes, Analysing complexity in classes of unary automatic structures, Language and automata theory and applications, Lecture Notes in Comput. Sci., vol. 5457, Springer, Berlin, 2009, pp. 518–529. MR 2544442, DOI 10.1007/978-3-642-00982-2_{4}4
Yuri V. Matiyasevich, Hilbert’s tenth problem, Foundations of Computing Series, MIT Press, Cambridge, MA, 1993. Translated from the 1993 Russian original by the author; With a foreword by Martin Davis. MR 1244324
André Nies, Describing groups, Bull. Symbolic Logic 13 (2007), no. 3, 305–339. MR 2359909, DOI 10.2178/bsl/1186666149
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
Joseph G. Rosenstein, Linear orderings, Pure and Applied Mathematics, vol. 98, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. MR 662564
S. Rubin. Automatic Structures. PhD thesis, University of Auckland, 2004.
Sasha Rubin, Automata presenting structures: a survey of the finite string case, Bull. Symbolic Logic 14 (2008), no. 2, 169–209. MR 2413002, DOI 10.2178/bsl/1208442827
Arto Salomaa and Matti Soittola, Automata-theoretic aspects of formal power series, Texts and Monographs in Computer Science, Springer-Verlag, New York-Heidelberg, 1978. MR 0483721
Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
Wolfgang Thomas, On frontiers of regular trees, RAIRO Inform. Théor. Appl. 20 (1986), no. 4, 371–381 (English, with French summary). MR 880841
Todor Tsankov, The additive group of the rationals does not have an automatic presentation, J. Symbolic Logic 76 (2011), no. 4, 1341–1351. MR 2895399, DOI 10.2178/jsl/1318338853
Andreas Weber, On the valuedness of finite transducers, Acta Inform. 27 (1990), no. 8, 749–780. MR 1080581, DOI 10.1007/BF00264285