TY - JOUR
T1 - The complexity of solution sets to equations in hyperbolic groups
AU - Ciobanu, Laura
AU - Elder, Murray
N1 - Funding Information:
Research supported by Australian Research Council (ARC) Project DP160100486, EPSRC grant EP/R035814/1, a Follow-On Grant from the International Centre of Mathematical Sciences (ICMS), Edinburgh, and an LMS Scheme 2 grant. Acknowledgements
Publisher Copyright:
© 2021, The Hebrew University of Jerusalem.
PY - 2021/11/25
Y1 - 2021/11/25
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85120629294&partnerID=8YFLogxK
U2 - 10.1007/s11856-021-2232-z
DO - 10.1007/s11856-021-2232-z
M3 - Article
AN - SCOPUS:85120629294
SN - 0021-2172
VL - 245
SP - 869
EP - 920
JO - Israel Journal of Mathematics
JF - Israel Journal of Mathematics
IS - 2
ER -