The complexity of solution sets to equations in hyperbolic groups

Laura Ciobanu*, Murray Elder

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

We show that the full set of solutions to systems of equations and inequations in a hyperbolic group, as shortlex geodesic words (or any regular set of quasigeodesic normal forms), is an EDT0L language whose specification can be computed in NSPACE(n2 log n) for the torsion-free case and NSPACE(n4 log n) in the torsion case. Furthermore, in the presence of effective quasi-isometrically embeddable rational constraints, we show that the full set of solutions to systems of equations in a hyperbolic group remains EDT0L. Our work combines the geometric results of Rips, Sela, Dahmani and Guirardel on the decidability of the existential theory of hyperbolic groups with the work of computer scientists including Plandowski, Jeż, Diekert and others on PSPACE algorithms to solve equations in free monoids and groups using compression, and involves an intricate language-theoretic analysis.

Original languageEnglish
Pages (from-to)869-920
Number of pages52
JournalIsrael Journal of Mathematics
Volume245
Issue number2
DOIs
Publication statusPublished - 25 Nov 2021

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'The complexity of solution sets to equations in hyperbolic groups'. Together they form a unique fingerprint.

Cite this