Solvability of equations in graph groups is decidable

被引：23
作者：
Diekert, Volker
Muscholl, Anca
机构：
[1] Univ Stuttgart, Inst Formale Methoden Informat, D-70569 Stuttgart, Germany
[2] Univ Paris 07, LIAFA, F-75251 Paris 05, France
来源：
INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION | 2006年 / 16卷 / 06期
关键词：
equations; graph groups; free partially commutative monoids;
D O I：
10.1142/S0218196706003372
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
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].
引用
收藏
页码：1047 / 1069
页数：23
相关论文
共 28 条
[1]   INHOMOGENEOUS SORTING [J].
ANISIMOV, AV ;
KNUTH, DE .
INTERNATIONAL JOURNAL OF COMPUTER & INFORMATION SCIENCES, 1979, 8 (04) :255-260
[2]   SUBGROUPS OF SEMIFREE GROUPS [J].
BAUDISCH, A .
ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1981, 38 (1-4) :19-28
[3]  
BENOIS M, 1969, CR ACAD SCI A MATH, V269, P1188
[4]  
Brady N, 2000, T AM MATH SOC, V353, P117
[5]  
Cartier P., 1969, LECT NOTES MATH
[6]  
Diekert V, 2003, LECT NOTES COMPUT SC, V2914, P156
[7]  
Diekert V, 2004, THEOR COMPUT SYST, V37, P133, DOI [10.1007/s0224-003-1110-x, 10.1007/s00224-003-1110-x]
[8]   Solving word equations modulo partial commutations [J].
Diekert, V ;
Matiyasevich, Y ;
Muscholl, A .
THEORETICAL COMPUTER SCIENCE, 1999, 224 (1-2) :215-235
[9]  
Diekert V, 2001, LECT NOTES COMPUT SC, V2076, P543
[10]  
Diekert V., 2001, LNCS, V2010, P170
123