We prove that the full solution set of a twisted word equation with regular constraints is an EDT0L language. It follows that the set of solutions to equations with rational constraints in a context-free group (= finitely generated virtually free group) in reduced normal forms is EDT0L. We can also decide whether or not the solution set is finite, which was an open problem. Moreover, this can all be done in PSPACE. Our results generalize the work by Lohrey and Senizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to complexity and with respect to expressive power. Both papers show that satisfiability is decidable, but neither gave any concrete complexity bound. Our results concern all solutions, and give, in some sense, the "optimal" formal language characterization.
展开▼
机译：我们证明具有规则约束的扭曲词方程的完整解集是EDT0L语言。由此得出，在归约法则形式下的无上下文组（=有限生成的虚拟组）中具有有理约束的方程组的解集为EDT0L。我们还可以决定解集是否有限，这是一个开放的问题。而且，这些都可以在PSPACE中完成。我们的结果概括了Lohrey和Senizergues（ICALP 2006）以及Dahmani和Guirardel（J. of Topology 2010）在复杂性和表达能力方面的工作。这两篇论文都表明，可满足性是可以决定的，但是都没有给出任何具体的复杂性界限。我们的结果涉及所有解决方案，并在某种意义上给出了“最佳”形式语言的表征。
展开▼
