Solutions sets to systems of equations in hyperbolic groups are EDT0L in PSPACE

Laura Ciobanu, Murray Elder

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)
5 Downloads (Pure)

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.

Original languageEnglish
Title of host publication46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
EditorsIoannis Chatzigiannakis, Christel Baier, Stefano Leonardi, Paola Flocchini
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume132
ISBN (Electronic)9783959771092
DOIs
Publication statusPublished - 2019
Event46th International Colloquium on Automata, Languages, and Programming 2019 - Patras, Greece
Duration: 8 Jul 201912 Jul 2019

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume132
ISSN (Electronic)1868-8969

Conference

Conference46th International Colloquium on Automata, Languages, and Programming 2019
Abbreviated titleICALP 2019
CountryGreece
CityPatras
Period8/07/1912/07/19

Keywords

  • EDT0L language
  • Existential theory
  • Hyperbolic group
  • PSPACE

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Solutions sets to systems of equations in hyperbolic groups are EDT0L in PSPACE'. Together they form a unique fingerprint.

  • Cite this

    Ciobanu, L., & Elder, M. (2019). Solutions sets to systems of equations in hyperbolic groups are EDT0L in PSPACE. In I. Chatzigiannakis, C. Baier, S. Leonardi, & P. Flocchini (Eds.), 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) (Vol. 132). [110] (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 132). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2019.110