论文标题
解决方案的复杂性与双曲线组的方程式集合
The complexity of solution sets to equations in hyperbolic groups
论文作者
论文摘要
我们表明，在双曲线组中，全套方程式和不等式系统的解决方案，作为Shortlex Geodesic单词（或任何常规的QuasigeOdesic正常形式），是一种EDT0L语言，可以在Nspace $（n^2 \ log n）$中计算，用于nspace $（n^2 \ log n）$，用于torsion-free-nspace case and nspace $（nspace $ n^n^4^4^4^4^4^4^4）$ n）此外，在存在准嵌入的有理约束的情况下，我们表明双曲线组中方程系统的完整解决方案仍然是EDT0L。我们的工作结合了RIPS，Sela，Dahmani和Guirardel的几何结果，涉及双曲线群体的存在理论与计算机科学家的工作，包括Plandowski，Je组，Diekert，Diekert和其他人在Pspace算法上在自由型和组中使用自由型和组中的旋转方程，并使用复杂的语言分析进行分析。
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ż, Diekert and others on PSPACE algorithms to solve equations in free monoids and groups using compression, and involves an intricate language-theoretic analysis.
