Document Open Access Logo

An Automaton Group with PSPACE-Complete Word Problem

Authors Jan Philipp Wächter , Armin Weiß

PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.6.pdf
  • Filesize: 0.62 MB
  • 17 pages

Document Identifiers

Author Details

Jan Philipp Wächter
  • Universität Stuttgart, Institut für Formale Methoden der Informatik (FMI), Universitätsstraße 38, 70569 Stuttgart, Germany
Armin Weiß
  • Universität Stuttgart, Institut für Formale Methoden der Informatik (FMI), Universitätsstraße 38, 70569 Stuttgart, Germany

Funding

  • Weiß, Armin: Funded by DFG project DI 435/7-1.

Cite As Get BibTex

Jan Philipp Wächter and Armin Weiß. An Automaton Group with PSPACE-Complete Word Problem. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.STACS.2020.6

Abstract

We construct an automaton group with a PSPACE-complete word problem, proving a conjecture due to Steinberg. Additionally, the constructed group has a provably more difficult, namely EXPSPACE-complete, compressed word problem. Our construction directly simulates the computation of a Turing machine in an automaton group and, therefore, seems to be quite versatile. It combines two ideas: the first one is a construction used by D'Angeli, Rodaro and the first author to obtain an inverse automaton semigroup with a PSPACE-complete word problem and the second one is to utilize a construction used by Barrington to simulate circuits of bounded degree and logarithmic depth in the group of even permutations over five elements.

Subject Classification

ACM Subject Classification
  • Theory of computation → Transducers
Keywords
  • automaton group
  • word problem
  • PSPACE
  • compressed word problem

Metrics

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

References

  1. Stanislav V. Aleshin. A free group of finite automata. Vestnik Moskovskogo Universiteta. Seriya I. Matematika, Mekhanika, 4:12-14, 1983. Google Scholar
  2. Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. Google Scholar
  3. David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC^1. J. Comput. Syst. Sci., 38(1):150-164, 1989. URL: https://doi.org/10.1016/0022-0000(89)90037-8.
  4. Laurent Bartholdi and Ivan Mitrofanov. The word and order problems for self-similar and automata groups. arXiv preprint, 2017. URL: http://arxiv.org/abs/1710.10109.
  5. Ievgen V. Bondarenko. Growth of Schreier graphs of automaton groups. Mathematische Annalen, 354(2):765-785, 2012. URL: https://doi.org/10.1007/s00208-011-0757-x.
  6. Ievgen V. Bondarenko. The word problem in Hanoi Towers groups. Algebra and Discrete Mathematics, 17(2):248-255, 2014. Google Scholar
  7. William W. Boone. The Word Problem. Annals of Mathematics, 70(2):207-265, 1959. Google Scholar
  8. Daniele D'Angeli, Emanuele Rodaro, and Jan Philipp Wächter. The structure theory of partial automaton semigroups. arXiv preprint, 2018. URL: http://arxiv.org/abs/1811.09420.
  9. Daniele D'Angeli, Emanuele Rodaro, and Jan Philipp Wächter. On the complexity of the word problem for automaton semigroups and automaton groups. Advances in Applied Mathematics, 90:160-187, 2017. URL: https://doi.org/10.1016/j.aam.2017.05.008.
  10. Max Dehn. Über unendliche diskontinuierliche Gruppen. Math. Ann., 71:116-144, 1911. Google Scholar
  11. Pierre Gillibert. Personal Communication. Google Scholar
  12. Pierre Gillibert. The finiteness problem for automaton semigroups is undecidable. International Journal of Algebra and Computation, 24(01):1-9, 2014. URL: https://doi.org/10.1142/S0218196714500015.
  13. Pierre Gillibert. An automaton group with undecidable order and Engel problems. Journal of Algebra, 497:363-392, 2018. URL: https://doi.org/10.1016/j.jalgebra.2017.11.049.
  14. Rostislav Grigorchuk and Igor Pak. Groups of intermediate growth: an introduction. L’Enseignement Mathématique, 54:251-272, 2008. Google Scholar
  15. Gennadií S. Makanin. Decidability of the universal and positive theories of a free group. Izv. Akad. Nauk SSSR, Ser. Mat. 48:735-749, 1984. In Russian; English translation in: Math. USSR Izvestija, 25, 75-88, 1985. Google Scholar
  16. Anatolij I. Mal'cev. On the equation zxyx^-1y^-1z^-1= aba^-1b^-1 in a free group. Akademiya Nauk SSSR. Sibirskoe Otdelenie. Institut Matematiki. Algebra i Logika, 1(5):45-50, 1962. Google Scholar
  17. Volodymyr V. Nekrashevych. Self-similar groups, volume 117 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2005. URL: https://doi.org/10.1090/surv/117.
  18. Petr S. Novikov. On the algorithmic unsolvability of the word problem in group theory. Trudy Mat. Inst. Steklov, pages 1-143, 1955. In Russian. Google Scholar
  19. Christos M. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Google Scholar
  20. David Robinson. Parallel Algorithms for Group Word Problems. PhD thesis, University of California, San Diego, 1993. Google Scholar
  21. Richard Edwin Stearns, Juris Hartmanis, and Philip M. Lewis. Hierarchies of memory limited computations. In 6th Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1965), pages 179-190. IEEE, 1965. Google Scholar
  22. Benjamin Steinberg. On some algorithmic properties of finite state automorphisms of rooted trees, volume 633 of Contemporary Mathematics, pages 115-123. American Mathematical Society, 2015. Google Scholar
  23. Zoran Šunić and Enric Ventura. The conjugacy problem in automaton groups is not solvable. Journal of Algebra, 364:148-154, 2012. URL: https://doi.org/10.1016/j.jalgebra.2012.04.014.
  24. Heribert Vollmer. Introduction to Circuit Complexity. Springer, Berlin, 1999. Google Scholar
  25. Mariya Vorobets and Yaroslav Vorobets. On a free group of transformations defined by an automaton. Geometriae Dedicata, 124:237-249, 2007. URL: https://doi.org/10.1007/s10711-006-9060-5.
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