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
Additional Information
- Dietrich Kuske
- Affiliation: Institut für Theoretische Informatik, TU Ilmenau, Postfach 100565, D-98684 Ilmenau, Germany
- Email: dietrich.kuske@tu-ilmenau.de
- Jiamou Liu
- Affiliation: Department of Computer Science, University of Aukland, Private Bag 92019, Auckland, New Zealand
- Email: liujiamou@gmail.com
- Markus Lohrey
- Affiliation: Institut für Informatik, Universität Leipzig, Augustusplatz 10-11, D-04109 Leipzig, Germany
- Email: lohrey@informatik.uni-leipzig.de
- 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
- © Copyright 2013 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 365 (2013), 5103-5151
- MSC (2010): Primary 03D05, 03D45, 03C57
- DOI: https://doi.org/10.1090/S0002-9947-2013-05766-2
- MathSciNet review: 3074369