Document Open Access Logo

Climbing up the Elementary Complexity Classes with Theories of Automatic Structures

Authors Faried Abu Zaid, Dietrich Kuske, Peter Lindner

PDF
Thumbnail PDF

File

LIPIcs.CSL.2018.3.pdf
  • Filesize: 471 kB
  • 16 pages

Document Identifiers

Author Details

Faried Abu Zaid
  • TU Ilmenau, Germany
Dietrich Kuske
  • TU Ilmenau, Germany
Peter Lindner
  • RWTH Aachen University, Germany

Cite As Get BibTex

Faried Abu Zaid, Dietrich Kuske, and Peter Lindner. Climbing up the Elementary Complexity Classes with Theories of Automatic Structures. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.CSL.2018.3

Abstract

Automatic structures are structures that admit a finite presentation via automata. Their most prominent feature is that their theories are decidable. In the literature, one finds automatic structures with non-elementary theory (e.g., the complete binary tree with equal-level predicate) and automatic structures whose theories are at most 3-fold exponential (e.g., Presburger arithmetic or infinite automatic graphs of bounded degree). This observation led Durand-Gasselin to the question whether there are automatic structures of arbitrary high elementary complexity.
We give a positive answer to this question. Namely, we show that for every h >=0 the forest of (infinitely many copies of) all finite trees of height at most h+2 is automatic and it's theory is complete for STA(*, exp_h(n, poly(n)), poly(n)), an alternating complexity class between h-fold exponential time and space. This exact determination of the complexity of the theory of these forests might be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity theory and logic
Keywords
  • Automatic Structures
  • Complexity Theory
  • Model Theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. V. Bárány, E. Grädel, and S. Rubin. Automata-based presentations of infinite structures. In Finite and Algorithmic Model Theory, pages 1-76. Cambridge University Press, 2011. Google Scholar
  2. L. Berman. The complexity of logical theories. Theoretical Computer Science, 11:71-77, 1980. Google Scholar
  3. A. Blumensath. Automatic structures. Technical report, RWTH Aachen, 1999. Google Scholar
  4. A. Blumensath and E. Grädel. Automatic Structures. In LICS'00, pages 51-62. IEEE Computer Society Press, 2000. Google Scholar
  5. Andrzej Ehrenfeucht. An application of games to the completeness problem for formalized theories. Fundamenta Mathematicae, 49(2):129-141, 1961. URL: http://eudml.org/doc/213582.
  6. C.C. Elgot. Decision problems of finite automata design and related arithmetics. Trans. Am. Math. Soc., 98:21-51, 1961. Google Scholar
  7. S. Feferman and R.L. Vaught. The first order properties of algebraic systems. Fund. Math., 47:57-103, 1959. Google Scholar
  8. J. Ferrante and Ch. Rackoff. The Computational Complexity of Logical Theories. Lecture Notes in Mathematics vol. 718. Springer, 1979. Google Scholar
  9. J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, Heidelberg, 2006. Google Scholar
  10. Markus Frick and Martin Grohe. The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic, 130(1-3):3-31, 2004. Google Scholar
  11. Ch. Frougny and J. Sakarovitch. Synchronized rational relations of finite and infinite words. Theor. Comput. Sci., 108:45-82, 1993. Google Scholar
  12. Jakub Gajarský and Petr Hlinený. Faster deciding MSO properties of trees of fixed height, and some consequences. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15-17, 2012, Hyderabad, India, pages 112-123, 2012. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.112.
  13. B.R. Hodgson. On direct products of automaton decidable theories. Theoretical Computer Science, 19:331-335, 1982. Google Scholar
  14. B. Khoussainov and M. Minnes. Three lectures on automatic structures. In Proceedings of Logic Colloquium, pages 132–-176, 2007. Google Scholar
  15. B. Khoussainov and A. Nerode. Automatic presentations of structures. In Logic and Computational Complexity, Lecture Notes in Comp. Science vol. 960, pages 367-392. Springer, 1995. Google Scholar
  16. B. Khoussainov, S. Rubin, and F. Stephan. Definability and regularity in automatic structures. In STACS'04, Lecture Notes in Comp. Science vol. 2996, pages 440-451. Springer, 2004. Google Scholar
  17. Bakhadyr Khoussainov, Jiamou Liu, and Mia Minnes. Unary automatic graphs: an algorithmic perspective. Mathematical Structures in Computer Science, 19(1):133-152, 2009. Google Scholar
  18. D. Kuske. Theories of automatic structures and their complexity. In CAI 2009, Lecture Notes in Comp. Science vol. 5725, pages 81-98. Springer, 2009. Google Scholar
  19. D. Kuske and M. Lohrey. Some natural decision problems in automatic graphs. Journal of Symbolic Logic, 75(2):678-710, 2010. Google Scholar
  20. D. Kuske and M. Lohrey. Automatic structures of bounded degree revisited. Journal of Symbolic Logic, 76(4):1352-1380, 2011. Google Scholar
  21. P. Lindner. Theorien automatischer Strukturen in der Exponentialzeithierarchie. Master’s thesis, TU Ilmenau, 2017. Google Scholar
  22. D.C. Oppen. A 2^2^2^cn upper bound on the complexity of Presburger arithmetic. Journal of Computer and System Sciences, 16:323-332, 1978. Google Scholar
  23. S. Rubin. Automata presenting structures: A survey of the finite string case. Bulletin of Symbolic Logic, 14:169-209, 2008. Google Scholar
  24. F. Stephan. Automatic structures - recent results and open questions. Journal of Physics: Conference Series, 632:012013, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact