Solvability of Equations in Graph Groups Is Decidable

Solvability of Equations in Graph Groups Is Decidable
复制标题

图群中方程的可解性是可判定的

DOI：
10.1142/s0218196706003372
复制
发表时间：
2006
期刊：
Int. J. Algebra Comput.
影响因子：
--
通讯作者：
A. Muscholl
A. Muscholl
中科院分区：
--
文献类型：
--
作者：
V. Diekert;A. Muscholl

文献摘要

被引文献

相似文献

我们证明了部分对合自由交换幺半群的存在性理论是可判定的。因此，图群的存在性理论也是可判定的。如果生成器的基本字母表是固定的，我们得到一个PSPACE完备性结果，否则（在统一设置）我们的决策过程是在EXPSPACE。我们的证明是文[6]的主要结果的一个简化.
We show that the existential theory of free partially commutative monoids with involution is decidable. As a consequence the existential theory of graph groups is also decidable. If the underlying alphabet of generators is fixed, we obtain a PSPACE-completeness result, otherwise (in the uniform setting) our decision procedure is in EXPSPACE. Our proof is a reduction to the main result of [6].