Word Equations over Graph Products
Word Equations over Graph Products
复制标题
图积上的字方程
DOI：
10.1142/s0218196708004548
复制
发表时间：
2003
影响因子：
--
通讯作者：
Markus Lohrey
中科院分区：
文献类型：
--
作者：
V. Diekert;Markus Lohrey
对于一类受限制的幺半群，我们证明了词方程存在论的可判定性在图的乘积下保持不变。此外，我们还证明了群的图积的正理论可以归结为某些因子么半群的正理论和其余因子的存在理论。这两个结果还包括对变量的适当约束。在许多情况下，较大类的约束会导致不可判定性结果。
For a restricted class of monoids, we prove that the decidability of the existential theory of word equations is preserved under graph products. Furthermore, we show that the positive theory of a graph product of groups can be reduced to the positive theories of some of the factor monoids and the existential theories of the remaining factors. Both results also include suitable constraints for the variables. Larger classes of constraints lead in many cases to undecidability results.