The complexity of solution sets to equations in hyperbolic groups
The complexity of solution sets to equations in hyperbolic groups
复制标题
双曲群方程解集的复杂度
DOI：
10.1007/s11856-021-2232-z
复制
发表时间：
2021
影响因子：
1
通讯作者：
Ciobanu L
中科院分区：
文献类型：
--
作者：
Ciobanu L
我们证明了双曲群中方程和不等式系统的解的全部集合，作为短线测地字（或任何拟测地范式的正则集），是一种EDT0L语言，其规范在无扭转情况下可以计算为inspace (n2logn)，在扭转情况下可以计算为nspace （n4logn）。进一步，在有效的拟等距可嵌入有理约束存在的情况下，我们证明了双曲群中方程组的全部解仍然是EDT0L。我们的工作结合了Rips， Sela， Dahmani和Guirardel关于双曲群存在理论的可决性的几何结果，以及包括Plandowski， jejez， Diekert和其他人在内的计算机科学家关于pspacealgorithms的工作，使用压缩来解决自由monoids和群中的方程，并涉及复杂的语言理论分析。
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 inNSPACE(n2logn) for the torsion-free case andNSPACE(n4logn) 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 onPSPACEalgorithms to solve equations in free monoids and groups using compression, and involves an intricate language-theoretic analysis.
登录
查看更多内容
关于单词双曲群的注释
DOI：
10.1007/s00039-003-0425-8
发表时间：
1991
期刊：
Geometric & Functional Analysis GAFA
影响因子：
--
作者：
J. Alonso;T. Brady;D. Cooper;V. Ferlini;Lustig;M. Mihalik;M. Shapiro;H. Short
通讯作者：
H. Short
非确定性线性空间中的词方程
DOI：
10.4230/lipics.icalp.2017.95
发表时间：
2022
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
Artur Jeż
通讯作者：
Artur Jeż
自由群中有理约束方程的存在主义理论是 PSPACE 完备的
影响因子：
1
作者：
V. Diekert;Claudio Gutiérrez;C. Hagenah
通讯作者：
C. Hagenah
自由群上的方程 w(x, y) = u：代数方法
DOI：
--
发表时间：
2007
期刊：
影响因子：
--
作者：
Nicholas W. M. Touikan
通讯作者：
Nicholas W. M. Touikan
有界自动机群是 co-ET0L
DOI：
--
发表时间：
2018
期刊：
Language and Automata Theory and Applications
影响因子：
--
作者：
A. Bishop;M. Elder
通讯作者：
M. Elder