Solutions to twisted word equations and equations in virtually free groups
Solutions to twisted word equations and equations in virtually free groups
复制标题
扭曲词方程和几乎自由群方程的解
DOI：
--
复制
发表时间：
2017
影响因子：
0.8
通讯作者：
M. Elder
中科院分区：
文献类型：
--
作者：
V. Diekert;M. Elder
众所周知，求解虚自由群中的方程问题可以归结为求解带对合的自由幺半群上带正则约束的扭字方程问题。本文证明了扭字方程的所有解的集合是一种EDT0L语言，它的规范可以在PSPACE中计算。在相同的复杂度范围内，我们可以决定解集是空的、有限的还是无限的。在本文的第二部分中，我们应用扭曲方程的结果，以获得在PSPACE的EDT0L描述的解决方案的一组方程的合理的约束条件下，生成的虚拟自由群在标准的正常形式相对于一个自然的一组发电机。如果有理约束是由一个固定的（或“足够小”的）有限幺半群的同态给出的，那么我们的算法可以在[公式：见正文]中实现，也就是在拟二次非确定性空间中实现。我们的结果推广了Lohrey和Sénizergues（ICALP 2006）以及Dahmani和Guirardel（J. of Topology 2010）在复杂性和表达能力方面的工作。这两篇论文都没有给出任何具体的复杂性界限，这些论文中的结果只针对解决方案的子集，而我们的结果涉及所有的解决方案。
It is well known that the problem solving equations in virtually free groups can be reduced to the problem of solving twisted word equations with regular constraints over free monoids with involution. In this paper, we prove that the set of all solutions of a twisted word equation is an EDT0L language whose specification can be computed in PSPACE . Within the same complexity bound we can decide whether the solution set is empty, finite, or infinite. In the second part of the paper we apply the results for twisted equations to obtain in PSPACE an EDT0L description of the solution set of equations with rational constraints for finitely generated virtually free groups in standard normal forms with respect to a natural set of generators. If the rational constraints are given by a homomorphism into a fixed (or “small enough”) finite monoid, then our algorithms can be implemented in [Formula: see text], that is, in quasi-quadratic nondeterministic space. Our results generalize the work by Lohrey and Sénizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to both complexity and expressive power. Neither paper gave any concrete complexity bound and the results in these papers are stated for subsets of solutions only, whereas our results concern all solutions.