Solution sets for equations over free groups are EDT0L languages
Solution sets for equations over free groups are EDT0L languages
复制标题
自由群方程的解集是 EDT0L 语言
DOI：
10.1142/s0218196716500363
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
M. Elder
中科院分区：
文献类型：
--
作者：
L. Ciobanu;V. Diekert;M. Elder
我们表明，给定一个方程在一个非线性生成的自由群，在减少的话的所有解决方案的集合形成一个有效的可构造的EDT 0 L语言。特别地，在简化词中的所有解的集合是Aho意义上的索引语言。我们给出的语言特征，以及进一步的问题的存在性或有限性的解决方案，遵循我们明确的建设有限有向图编码的所有解决方案。我们的结果结合了最近发明的再压缩技术的Jez，和一个新的方式来整合的线性丢番图方程的解决方案的过程。
作为我们的技术的副产品，我们将复杂性从以前的作品中的二次非确定性空间提高到$\mathsf{NSPACE}（n\log n）$。
We show that, given an equation over a finitely generated free group, the set of all solutions in reduced words forms an effectively constructible EDT0L language. In particular, the set of all solutions in reduced words is an indexed language in the sense of Aho. The language characterization we give, as well as further questions about the existence or finiteness of solutions, follow from our explicit construction of a finite directed graph which encodes all the solutions. Our result incorporates the recently invented recompression technique of Jez, and a new way to integrate solutions of linear Diophantine equations into the process.
As a byproduct of our techniques, we improve the complexity from quadratic nondeterministic space in previous works to $\mathsf{NSPACE}(n\log n)$ here.