Document Open Access Logo

Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups

Authors Volker Diekert, Murray Elder

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.96.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Volker Diekert
Murray Elder

Cite As Get BibTex

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 (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 96:1-96:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.96

Abstract

We prove that the full solution set of a twisted word equation with regular constraints is an  EDT0L language. It follows that the set of solutions to equations with rational constraints in a context-free group (= finitely generated virtually free group) in reduced normal forms is EDT0L. We can also decide  whether or not the solution set is finite, which was an open problem. Moreover, this can all be done in PSPACE. Our results generalize the work by  Lohrey and Senizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to complexity and with respect to expressive power. Both papers show that satisfiability is decidable, but neither gave any concrete complexity bound. Our results concern all solutions, and  give, in some sense, the "optimal" formal language characterization.

Subject Classification

Keywords
  • Twisted word equation
  • EDT0L
  • virtually free group
  • context-free group

Metrics

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

References

  1. Peter R. J. Asveld. Controlled iteration grammars and full hyper-AFL’s. Information and Control, 34(3):248-269, 1977. URL: http://dx.doi.org/10.1016/S0019-9958(77)90308-4.
  2. Gilbert Baumslag, Alexei Myasnikov, and Vladimir Remeslennikov. Algebraic geometry over groups. In Algorithmic problems in groups and semigroups (Lincoln, NE, 1998), Trends Math., pages 35-50. Birkhäuser Boston, Boston, MA, 2000. URL: http://dx.doi.org/10.1007/978-1-4612-1388-8_3.
  3. 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. Conference version in ICALP 2015, LNCS 9135. URL: http://dx.doi.org/10.1142/S0218196716500363.
  4. 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.
  5. Volker Diekert and Murray Elder. Solutions of twisted word equations, EDT0L languages, and context-free groups. ArXiv e-prints, January 2017. URL: https://arxiv.org/abs/1701.03297, URL: http://arxiv.org/abs/1701.03297.
  6. 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. Conference version in Proc. CSR 2014, LNCS 8476 (2014). URL: http://dx.doi.org/10.1016/j.ic.2016.09.009.
  7. Volker Diekert and Armin Weiß. Context-free groups and Bass-Serre theory. ArXiv e-prints, July 2013. URL: http://arxiv.org/abs/1307.8297.
  8. Martin J. Dunwoody. The accessibility of finitely presented groups. Inventiones Mathematicae, 81(3):449-457, 1985. URL: http://dx.doi.org/10.1007/BF01388581.
  9. Andrzej Ehrenfeucht and Grzegorz Rozenberg. On some context free languages that are not deterministic ET0L languages. RAIRO Theor. Inform. Appl., 11:273-291, 1977. Google Scholar
  10. Samuel Eilenberg. Automata, languages, and machines. Vol. A. Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York, 1974. Pure and Applied Mathematics, Vol. 58. Google Scholar
  11. Julien Ferté, Nathalie Marin, and Géraud Sénizergues. Word-mappings of level 2. Theory Comput. Syst., 54:111-148, 2014. URL: http://dx.doi.org/10.1007/s00224-013-9489-5.
  12. Robert H. Gilman. Personal communication, 2012. Google Scholar
  13. Robert H. Gilman, Susan Hermiller, Derek F. Holt, and Sarah Rees. A characterisation of virtually free groups. Arch. Math. (Basel), 89(4):289-295, 2007. URL: http://dx.doi.org/10.1007/s00013-007-2206-3.
  14. Mikhael 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.
  15. Sanjay Jain, Alexei Miasnikov, and Frank Stephan. The complexity of verbal languages over groups. In Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 405-414. IEEE Computer Soc., Los Alamitos, CA, 2012. URL: http://dx.doi.org/10.1109/LICS.2012.50.
  16. Artur Jeż. Recompression: a simple and powerful technique for word equations. J. ACM, 63(1):Art. 4, 51, 2016. Conference version in Proc. STACS 2013. URL: http://dx.doi.org/10.1145/2743014.
  17. Artur Jeż. Word Equations in Nondeterministic Linear Space, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.95.
  18. Abe Karrass, Alfred Pietrowski, and Donald Solitar. Finite and infinite cyclic extensions of free groups. J. Austral. Math. Soc., 16:458-466, 1973. Collection of articles dedicated to the memory of Hanna Neumann, IV. URL: http://dx.doi.org/10.1017/S1446788700015445.
  19. Dietrich Kuske and Markus Lohrey. Logical aspects of Cayley-graphs: the group case. Ann. Pure Appl. Logic, 131(1-3):263-286, 2005. URL: http://dx.doi.org/10.1016/j.apal.2004.06.002.
  20. Markus Lohrey and Géraud Sénizergues. Theories of HNN-extensions and amalgamated products. In Automata, languages and programming. Part II, volume 4052 of Lecture Notes in Comput. Sci., pages 504-515. Springer, Berlin, 2006. URL: http://dx.doi.org/10.1007/11787006_43.
  21. Gennadií S. Makanin. The problem of solvability of equations in a free semigroup. Math. Sbornik, 103:147-236, 1977. English transl. in Math. USSR Sbornik 32 (1977). Google Scholar
  22. Victor Mazurov and Evgeny Khukhro. Unsolved Problems in Group Theory. The Kourovka Notebook. No. 18 (English version). ArXiv e-prints, January 2014. URL: http://arxiv.org/abs/1401.0300.
  23. David E. Muller and Paul E. Schupp. Groups, the theory of ends, and context-free languages. J. Comput. System Sci., 26(3):295-310, 1983. URL: http://dx.doi.org/10.1016/0022-0000(83)90003-X.
  24. Wojciech Plandowski. Satisfiability of word equations with constants is in PSPACE. Journal of the ACM, 51:483-496, 2004. Conference version in FOCS'99. URL: http://dx.doi.org/doi:10.1145/990308.990312.
  25. Wojciech Plandowski and Wojciech Rytter. Application of Lempel-Ziv encodings to the solution of word equations. In K. G. Larsen et al., editors, Proc. 25th International Colloquium Automata, Languages and Programming (ICALP'98), Aalborg (Denmark), 1998, volume 1443 of Lecture Notes in Computer Science, pages 731-742, Heidelberg, 1998. Springer-Verlag. Google Scholar
  26. Eliyahu Rips and Zlil Sela. Canonical representatives and equations in hyperbolic groups. Invent. Math., 120(3):489-512, 1995. URL: http://dx.doi.org/10.1007/BF01241140.
  27. Grzegorz Rozenberg and Arto Salomaa. The Book of L. Springer, 1986. Google Scholar
  28. Grzegorz Rozenberg and Arto Salomaa, editors. Handbook of formal languages. Vol. 1. Springer-Verlag, Berlin, 1997. Word, language, grammar. URL: http://dx.doi.org/10.1007/978-3-642-59126-6.
  29. Géraud Sénizergues. An effective version of Stallings' theorem in the case of context-free groups. In Automata, languages and programming (Lund, 1993), volume 700 of Lecture Notes in Comput. Sci., pages 478-495. Springer, Berlin, 1993. URL: http://dx.doi.org/10.1007/3-540-56939-1_96.
  30. Géraud Sénizergues. On the finite subgroups of a context-free group. In Geometric and computational perspectives on infinite groups (Minneapolis, MN and New Brunswick, NJ, 1994), volume 25 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 201-212. Amer. Math. Soc., Providence, RI, 1996. Google Scholar
  31. Jean-Pierre Serre. Trees. Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2003. Translated from the French original by John Stillwell, Corrected 2nd printing of the 1980 English translation. 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