License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.110
URN: urn:nbn:de:0030-drops-106867
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10686/
Go to the corresponding LIPIcs Volume Portal

Ciobanu, Laura ; Elder, Murray

Solutions Sets to Systems of Equations in Hyperbolic Groups Are EDT0L in PSPACE

pdf-format:
LIPIcs-ICALP-2019-110.pdf (0.6 MB)

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, Jez, 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.

BibTeX - Entry

@InProceedings{ciobanu_et_al:LIPIcs:2019:10686,
  author =	{Laura Ciobanu and Murray Elder},
  title =	{{Solutions Sets to Systems of Equations in Hyperbolic Groups Are EDT0L in PSPACE}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{110:1--110:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10686},
  URN =		{urn:nbn:de:0030-drops-106867},
  doi =		{10.4230/LIPIcs.ICALP.2019.110},
  annote =	{Keywords: Hyperbolic group, Existential theory, EDT0L language, PSPACE}
}

Keywords: Hyperbolic group, Existential theory, EDT0L language, PSPACE
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI