{
  "id": "2001.09591",
  "version": "v1",
  "published": "2020-01-27T05:49:32.000Z",
  "updated": "2020-01-27T05:49:32.000Z",
  "title": "The complexity of solution sets to equations in hyperbolic groups",
  "authors": [
    "Laura Ciobanu",
    "Murray Elder"
  ],
  "comment": "32 pages, 3 figures, 1 table. An extended abstract of a preliminary version of this paper was presented at the conference ICALP 2019, arXiv:1902.07349",
  "categories": [
    "math.GR",
    "cs.FL"
  ],
  "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$(n^2\\log n)$ for the torsion-free case and NSPACE$(n^4\\log n)$ in the torsion case. Furthermore, in the presence of 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\\.z, Diekert and others on PSPACE algorithms to solve equations in free monoids and groups using compression, and involves an intricate language-theoretic analysis.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-01-27T05:49:32.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03D05",
      "20F65",
      "20F70",
      "68Q25",
      "68Q45"
    ],
    "keywords": [
      "solution sets",
      "full set",
      "hyperbolic group remains edt0l",
      "complexity",
      "intricate language-theoretic analysis"
    ],
    "tags": [
      "conference paper"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 32,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}