Document Open Access Logo

Solutions Sets to Systems of Equations in Hyperbolic Groups Are EDT0L in PSPACE (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors Laura Ciobanu , Murray Elder

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.110.pdf
  • Filesize: 0.59 MB
  • 15 pages

Document Identifiers

Author Details

Laura Ciobanu
  • Heriot-Watt University, Edinburgh EH14 4AS, Scotland
Murray Elder
  • University of Technology Sydney, Ultimo NSW 2007, Australia

Funding

Research supported by Australian Research Council (ARC) Project DP160100486, and a Follow-On Grant from the International Centre of Mathematical Sciences (ICMS), Edinburgh.
  • Ciobanu, Laura: Supported by EPSRC grant EP/R035814/1.

Acknowledgements

The authors wish to thank Yago Antolín, Alex Bishop, François Dahmani, Volker Diekert, Michal Ferov and Jim Howie for helpful conversations, and the anonymous reviewers for their feedback and corrections.

Cite AsGet BibTex

Laura Ciobanu and Murray Elder. Solutions Sets to Systems of Equations in Hyperbolic Groups Are EDT0L in PSPACE (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 110:1-110:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.110

Abstract

We show that the full set of solutions to systems of equations and inequations in a hyperbolic group, with or without torsion, as shortlex geodesic words, is an EDT0L language whose specification can be computed in NSPACE(n^2 log n) for the torsion-free case and NSPACE(n^4 log n) for the torsion case. Our work combines deep geometric results by Rips, Sela, Dahmani and Guirardel on decidability of existential theories of hyperbolic groups, work of computer scientists including Plandowski, Jeż, Diekert and others on PSPACE algorithms to solve equations in free monoids and groups using compression, and an intricate language-theoretic analysis. The present work gives an essentially optimal formal language description for all solutions in all hyperbolic groups, and an explicit and surprising low space complexity to compute them.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
  • Theory of computation → Grammars and context-free languages
  • Theory of computation → Complexity classes
  • Mathematics of computing → Combinatorics on words
Keywords
  • Hyperbolic group
  • Existential theory
  • EDT0L language
  • PSPACE

Metrics

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

Related Versions

References

  1. J. M. Alonso, T. Brady, D. Cooper, V. Ferlini, M. Lustig, M. Mihalik, M. Shapiro, and H. Short. Notes on word hyperbolic groups. In Group theory from a geometrical viewpoint (Trieste, 1990), pages 3-63. World Sci. Publ., River Edge, NJ, 1991. Google Scholar
  2. Peter R. J. Asveld. Controlled iteration grammars and full hyper-AFL’s. Information and Control, 34(3):248-269, 1977. Google Scholar
  3. Peter R.J. Asveld. A Characterization of ET0L and EDT0L Languages. Number 129 in Memorandum / Department of Applied Mathematics. Department of Applied Mathematics, University of Twente, 1976. Google Scholar
  4. Alex Bishop and Murray Elder. Bounded Automata Groups are co-ET0L. In Carlos Martín-Vide, Alexander Okhotin, and Dana Shapira, editors, Language and Automata Theory and Applications, pages 82-94, Cham, 2019. Springer International Publishing. Google Scholar
  5. Tara Brough, Laura Ciobanu, Murray Elder, and Georg Zetzsche. Permutations of context-free, ET0L and indexed languages. Discrete Math. Theor. Comput. Sci., 17(3):167-178, 2016. Google Scholar
  6. James W. Cannon. The theory of negatively curved spaces and groups. In Ergodic theory, symbolic dynamics, and hyperbolic spaces (Trieste, 1989), Oxford Sci. Publ., pages 315-369. Oxford Univ. Press, New York, 1991. Google Scholar
  7. Laura Ciobanu, Volker Diekert, and Murray Elder. Solution sets for equations over free groups are EDT0L languages. Internat. J. Algebra Comput., 26(5):843-886, 2016. URL: http://dx.doi.org/10.1142/S0218196716500363.
  8. Laura Ciobanu and Murray Elder. Solutions sets to systems of equations in hyperbolic groups are EDT0L in PSPACE. arXiv e-prints, abs/1902.07349, February 2019. URL: http://arxiv.org/abs/1902.07349.
  9. Laura Ciobanu, Murray Elder, and Michal Ferov. Applications of L systems to group theory. Internat. J. Algebra Comput., 28(2):309-329, 2018. URL: http://dx.doi.org/10.1142/S0218196718500145.
  10. Karel Culik, II. On some families of languages related to developmental systems. Internat. J. Comput. Math., 4:31-42, 1974. URL: http://dx.doi.org/10.1080/00207167408803079.
  11. François Dahmani and Vincent Guirardel. Foliations for solving equations in groups: free, virtually free, and hyperbolic groups. J. Topol., 3(2):343-404, 2010. URL: http://dx.doi.org/10.1112/jtopol/jtq010.
  12. François Dahmani and Vincent Guirardel. The isomorphism problem for all hyperbolic groups. Geom. Funct. Anal., 21(2):223-300, 2011. URL: http://dx.doi.org/10.1007/s00039-011-0120-0.
  13. T. Delzant. L'image d'un groupe dans un groupe hyperbolique. Comment. Math. Helv., 70(2):267-284, 1995. URL: http://dx.doi.org/10.1007/BF02566008.
  14. Volker Diekert and Murray Elder. Solutions of twisted word equations, EDT0L languages, and context-free groups. In 44th International Colloquium on Automata, Languages, and Programming, volume 80 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 96, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017. Google Scholar
  15. Volker Diekert and Murray Elder. Solutions to twisted word equations and equations in virtually free groups. arXiv e-prints, January 2017. URL: http://arxiv.org/abs/1701.03297.
  16. Volker Diekert, Claudio Gutiérrez, and Christian Hagenah. The existential theory of equations with rational constraints in free groups is PSPACE-complete. In A. Ferreira and H. Reichel, editors, Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS'01), Dresden (Germany), 2001, volume 2010 of Lecture Notes in Computer Science, pages 170-182. Springer-Verlag, 2001. URL: http://dx.doi.org/10.1007/3-540-44693-1_15.
  17. Volker Diekert, Artur Jeż, and Manfred Kufleitner. Solutions of word equations over partially commutative structures. In 43rd International Colloquium on Automata, Languages, and Programming, volume 55 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 127, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016. Google Scholar
  18. Volker Diekert, Artur Jeż, and Wojciech Plandowski. Finding all solutions of equations in free groups and monoids with involution. Inform. and Comput., 251:263-286, 2016. URL: http://dx.doi.org/10.1016/j.ic.2016.09.009.
  19. A. Ehrenfeucht and G. Rozenberg. On Decomposing Some ET0L Languages Into Deterministic ET0L Languages, 1974. CU-CS-045-74. Computer Science Technical Reports (44). URL: https://scholar.colorado.edu/csci_techreports/44.
  20. A. Ehrenfeucht and G. Rozenberg. On inverse homomorphic images of deterministic ET0L languages. In Automata, languages, development, pages 179-189. North-Holland, Amsterdam, 1976. Google Scholar
  21. David Epstein and Derek Holt. The linearity of the conjugacy problem in word-hyperbolic groups. Internat. J. Algebra Comput., 16(2):287-305, 2006. URL: http://dx.doi.org/10.1142/S0218196706002986.
  22. 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. Google Scholar
  23. Robert H. Gilman. On the definition of word hyperbolic groups. Math. Z., 242(3):529-541, 2002. Google Scholar
  24. R. I. Grigorchuk and I. G. Lysionok. A description of solutions of quadratic equations in hyperbolic groups. Internat. J. Algebra Comput., 2(3):237-274, 1992. URL: http://dx.doi.org/10.1142/S0218196792000153.
  25. M. Gromov. Hyperbolic groups. In Essays in group theory, volume 8 of Math. Sci. Res. Inst. Publ., pages 75-263. Springer, New York, 1987. URL: http://dx.doi.org/10.1007/978-1-4613-9586-7_3.
  26. M. Gromov. Random walk in random groups. Geom. Funct. Anal., 13(1):73-146, 2003. URL: http://dx.doi.org/10.1007/s000390300002.
  27. Derek F. Holt. Word-hyperbolic groups have real-time word problem. Internat. J. Algebra Comput., 10(2):221-227, 2000. URL: http://dx.doi.org/10.1142/S0218196700000078.
  28. Derek F. Holt, Markus Lohrey, and Saul Schleimer. Compressed decision problems in hyperbolic groups. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 34 of LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2019.34.
  29. Derek F. Holt and Sarah Rees. Regularity of quasigeodesics in a hyperbolic group. Internat. J. Algebra Comput., 13(5):585-596, 2003. URL: http://dx.doi.org/10.1142/S0218196703001560.
  30. Artur Jeż. Recompression: a simple and powerful technique for word equations. J. ACM, 63(1):Art. 4, 51, 2016. URL: http://dx.doi.org/10.1145/2743014.
  31. Artur Jeż. Word equations in nondeterministic linear space. In 44th International Colloquium on Automata, Languages, and Programming, volume 80 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 95, 13. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017. Google Scholar
  32. Lila Kari, Grzegorz Rozenberg, and Arto Salomaa. L systems. In Handbook of formal languages, Vol. 1, pages 253-328. Springer, Berlin, 1997. Google Scholar
  33. Olga Kharlampovich and Alexei Myasnikov. Definable sets in a hyperbolic group. Internat. J. Algebra Comput., 23(1):91-110, 2013. URL: http://dx.doi.org/10.1142/S021819671350001X.
  34. Manfred Kufleitner. Wortgleichungen in hyperbolischen Gruppen. Diplomarbeit, Universität Stuttgart, Fakultät Informatik, Germany, July 2001. URL: http://www2.informatik.uni-stuttgart.de/cgi-bin/NCSTRL/NCSTRL_view.pl?id=DIP-1922&engl=0.
  35. I. G. Lysionok. Some algorithmic properties of hyperbolic groups. Izv. Akad. Nauk SSSR Ser. Mat., 53(4):814-832, 912, 1989. URL: http://dx.doi.org/10.1070/IM1990v035n01ABEH000693.
  36. Gennadií Semyonovich Makanin. Equations in a free group. Izv. Akad. Nauk SSR, Ser. Math. 46:1199-1273, 1983. English transl. in Math. USSR Izv. 21 (1983). Google Scholar
  37. A. Yu. Ol\cprime shanskiĭ. Almost every group is hyperbolic. Internat. J. Algebra Comput., 2(1):1-17, 1992. URL: http://dx.doi.org/10.1142/S0218196792000025.
  38. Wojciech Plandowski. Satisfiability of word equations with constants is in PSPACE. J. ACM, 51(3):483-496, 2004. URL: http://dx.doi.org/10.1145/990308.990312.
  39. E. Rips and Z. Sela. Canonical representatives and equations in hyperbolic groups. Invent. Math., 120(3):489-512, 1995. URL: http://dx.doi.org/10.1007/BF01241140.
  40. Z. Sela. Diophantine geometry over groups and the elementary theory of free and hyperbolic groups. In Proceedings of the International Congress of Mathematicians, Vol. II (Beijing, 2002), pages 87-92. Higher Ed. Press, Beijing, 2002. Google Scholar
  41. L. Silberman. Addendum to: "Random walk in random groups" [Geom. Funct. Anal. 13 (2003), no. 1, 73-146; MR1978492] by M. Gromov. Geom. Funct. Anal., 13(1):147-177, 2003. URL: http://dx.doi.org/10.1007/s000390300003.
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 Imprint Privacy Contact