Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-26T12:55:55.321Z Has data issue: false hasContentIssue false
  • English
  • Français

Automatic structures of bounded degree revisited

Published online by Cambridge University Press:  12 March 2014

Dietrich Kuske  and
Markus Lohrey
Dietrich Kuske
Affiliation:
Technische Universität Ilmenau, Institut für Theoretische Informatik, Ilmenau, Germany, E-mail: [email protected]
Markus Lohrey
Affiliation:
Universität Leipzig, Institut für Informatik, Leipzig, Germany, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The first-order theory of a string automatic structure is known to be decidable, but there are examples of string automatic structures with nonelementary first-order theories. We prove that the first-order theory of a string automatic structure of bounded degree is decidable in doubly exponential space (for injective automatic presentations, this holds even uniformly). This result is shown to be optimal since we also present a string automatic structure of bounded degree whose first-order theory is hard for 2EXPSPACE. We prove similar results also for tree automatic structures. These findings close the gaps left open in [28] by improving both the lower and the upper bounds.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 76 , Issue 4 , December 2011 , pp. 1352 - 1380
Copyright
Copyright © Association for Symbolic Logic 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Bárány, V., Invariants of automatic presentations and semi-synchronous transductions, Proceedings of STACS'06, Lecture Notes in Computer Science, vol. 3884, Springer, 2006, pp. 289–300.Google Scholar
[2] Bárány, V., Automatic presentations of infinite structure, Ph.D. thesis, RWTH Aachen, 2007.Google Scholar
[3] Bárány, V., Grädel, E., and Rubin, S., Automata-based presentations of infinite structures, Finite and algorithmic model theory (Esparza, J., Michaux, C., and Steinhorn, C., editors), London Mathematical Society Lecture Note Series, no. 379, Cambridge University Press, 2011, pp. 1–76.Google Scholar
[4] Bárány, V., Kaiser, ᴌ., and Rubin, S., Cardinality and counting quantifiers on omega-automatic structures, Proceedings of STACS'08 (Albers, S. and Weil, P., editors), IFIB Schloss Dagstuhl, 2008, pp. 385–396.Google Scholar
[5] Benedikt, M., Libkin, L., Schwentick, Th., and Segoufin, L., Definable relations and first-order query languages over strings, Journal of the ACM, vol. 50 (2003), no. 5, pp. 694–751.CrossRefGoogle Scholar
[6] Blumensath, A., Automatic structures, Diploma Thesis, RWTH Aachen, 1999.Google Scholar
[7] Blumensath, A. and Grädel, E., Automatic structures, Proceedings of LICS'00, IEEE Computer Society Press, 2000, pp. 51–62.Google Scholar
[8] Chandra, A. K., Kozen, D. C., and Stockmeyer, L. J., Alternation, Journal of the ACM, vol. 28 (1981), no. 1, pp. 114–133.CrossRefGoogle Scholar
[9] Colcombet, Th. and Löding, Ch., Transforming structures by set interpretations, Logical Methods in Computer Science, vol. 3 (2007), pp. 1–36.Google Scholar
[10] Comon, H., Dauchet, M., Gilleron, R., Löding, C., Jacquemard, F., Lugiez, D., Tison, S., and Tommasi, M., Tree automata techniques and applications, available on http://www.grappa.univlille3.fr/tata, release 10, 12th 2007, 2007.Google Scholar
[11] Compton, K. J. and Henson, C. W., A uniform method for proving lower bounds on the computational complexity of logical theories, Annals of Pure and Applied Logic, vol. 48 (1990), pp. 1–79.CrossRefGoogle Scholar
[12] Dawar, A., Grohe, M., Kreutzer, St., and Schweikardt, N., Model theory makes formulas large, Proceedings of ICALP 2007 (Arge, L., Cachin, C., Jurdzinski, T., and Tarlecki, A., editors), Lecture Notes in Computer Science, vol. 4596, Springer, 2007, pp. 913–924.Google Scholar
[13] Delhommé, Ch., Goranko, V., and Knapik, T., Automatic linear orderings, manuscript, 2003.Google Scholar
[14] Elgot, C. C., Decision problems of finite automata design and related arithmetics, Transactions of the American Mathematical Society, vol. 98 (1961), pp. 21–51.CrossRefGoogle Scholar
[15] Epstein, D. B. A., Cannon, J. W., Holt, D. F., Levy, S. V. F., Paterson, M. S., and Thurston, W. P., Word processing in groups, Jones and Bartlett Publishers, Boston, 1992.CrossRefGoogle Scholar
[16] Gaifman, H., On local and nonlocal properties, Logic colloquium '81 (Stern, J., editor), North-Holland, 1982, pp. 105–135.Google Scholar
[17] Hjorth, G., Khoussainov, B., Montalbán, A., and Nibs, A., From automatic structures to Borel structures, Proceedings of LICS'08, IEEE Computer Society, 2008, pp. 431–441.Google Scholar
[18] Hodgson, B. R., On direct products of automaton decidable theories, Theoretical Computer Science, vol. 19 (1982), pp. 331–335.CrossRefGoogle Scholar
[19] Ishihara, I., Khoussainov, B., and Rubin, S., Some results on automatic structures, Proceedings of LICS'02, IEEE Computer Society Press, 2002, pp. 235–244.Google Scholar
[20] Khoussainov, B. and Nerode, A., Automatic presentations of structures, Logic and computational complexity (Leivant, D., editor), Lecture Notes in Computer Science, vol. 960, Springer, 1995, pp. 367–392.CrossRefGoogle Scholar
[21] Khoussainov, B. and Rubin, S., Graphs with automatic presentations over a unary alphabet, Journal of Automata, Languages and Combinatorics, vol. 6 (2001), pp. 467–480.Google Scholar
[22] Khoussainov, B., Rubin, S., and Stephan, F., On automatic partial orders, Proceedings of LICS'03, IEEE Computer Society Press, 2003, pp. 168–177.Google Scholar
[23] Khoussainov, B., Definability and regularity in automatic structures, Proceedings of STACS'04 (Diekert, V. and Habib, M., editors), Lecture Notes in Computer Science, vol. 2996, Springer, 2004, pp. 440–451.Google Scholar
[24] Kuske, D., IS Cantor's theorem automatic?, Proceedings of LPAR'05 (Vardi, M. Y. and Voronkov, A., editors), Lecture Notes in Computer Science, vol. 2850, Springer, 2003, pp. 332–345.Google Scholar
[25] Kuske, D., Theories of automatic structures and their complexity, Proceedings of CAI'09 (Bozapalidis, S. and Rahonis, G., editors), Lecture Notes in Computer Science, vol. 5725, 2009, pp. 81–98.Google Scholar
[26] Kuske, D. and Lohrey, M., First-order and counting theories of ω-automatic structures, this Journal, vol. 73 (2008), pp. 129–150.Google Scholar
[27] Kuske, D., Some natural decision problems in automatic graphs, this Journal, vol. 75 (2010), no. 2, pp. 678–710.Google Scholar
[28] Lohrey, M., Automatic structures of bounded degree, Proceedings of LPAR'O3 (Vardi, M. Y. and Voronkov, A., editors), Lecture Notes in Computer Science, vol. 2850, Springer, 2003, pp. 344–358.Google Scholar
[29] Meyer, A. R., Weak monadic second order theory of one successor is not elementary recursive, Logic colloquium (Parikh, R., editor), Lecture Notes in Mathematics, vol. 453, Springer, 1975, pp. 132–154.CrossRefGoogle Scholar
[30] Papadimitriou, C. H., Computational complexity, Addison Wesley, 1994.Google Scholar
[31] Rubin, S., Automata presenting structures: A survey of the finite string case, The Bulletin of Symbolic Logic, vol. 14 (2008), pp. 169–209.CrossRefGoogle Scholar
[32] Seidl, H., Single-valuedness of tree transducers is decidable in polynomial time, Theoretical Computer Science, vol. 106 (1992), pp. 135–181.CrossRefGoogle Scholar
[33] Silva, P. V. and Steinberg, B., A geometric characterization of automatic monoids, Quarterly Journal of Mathematics, vol. 55 (2004), pp. 333–356.CrossRefGoogle Scholar
[34] Weber, A., On the valuedness of finite transducers, Acta Informatica, vol. 27 (1990), pp. 749–780.CrossRefGoogle Scholar
[35] Weidner, Th., Die Größe injektiver baumautomatischer Darstellungen und die Komplexität ihrer Berechnung, Diploma thesis, University of Leipzig, 2010, in German. English version in preparation.Google Scholar