Existential and Positive Theories of Equations in Graph Products
Existential and Positive Theories of Equations in Graph Products
复制标题
图积方程的存在理论和实证理论
DOI：
10.1007/s00224-003-1110-x
复制
发表时间：
2002
影响因子：
0.5
通讯作者：
Markus Lohrey
中科院分区：
文献类型：
--
作者：
V. Diekert;Markus Lohrey
摘要
我们证明了方程的存在理论
中的归一化理性约束
有限么半群、自由么半群和
自由组是PSPACE-Complete。
在一定的限制下，这一结果也成立
如果图形产品是输入的一部分。
作为第二个主要结果，我们证明了方程的正定理论
具有可识别的限制
在图中有限群和自由群的乘积是
可以决定的。
Abstract
We prove that the existential theory of equations
with normalized rational constraints in
a fixed graph product of finite monoids, free monoids, and
free groups is PSPACE-complete.
Under certain restrictions this result also holds
if the graph product is part of the input.
As the second main result we prove that the positive theory of equations
with recognizable constraints
in graph products of finite and free groups is
decidable.