×

Word equations over graph products. (English) Zbl 1186.20041

The existence of algorithms recognizing the solvability of equations in a free semigroup was established by G. S. Makanin more than four decades ago and has prompted a wealth of research, well referenced in the paper under review. The authors continue this stream of research by establishing transfer results to graph products (a construction that generalizes both free and direct products) of monoids.
From the summary: “For monoids that satisfy a weak cancellation condition it is shown that the decidability of the existential theory of word equations is preserved under graph products. Furthermore, it is shown that the positive theory of a graph product of groups can be reduced to the positive theories of those factors which commute with all other factors 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.”

MSC:

20M05 Free semigroups, generators and relations, word problems
03B25 Decidability of theories and sets of sentences
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20E06 Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations
03D35 Undecidability and degrees of sets of sentences
68Q70 Algebraic theory of languages and automata
68Q42 Grammars and rewriting systems
20F70 Algebraic geometry over groups; equations over groups
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1007/BF02088289 · Zbl 0679.68132
[2] DOI: 10.1007/BF01895842 · Zbl 0381.20027
[3] DOI: 10.1007/BF01917515
[4] DOI: 10.1016/0022-4049(91)90139-S · Zbl 0749.20006
[5] DOI: 10.1016/0304-3975(80)90037-7 · Zbl 0475.03017
[6] DOI: 10.1007/978-3-663-09367-1
[7] DOI: 10.1007/978-1-4613-9771-7
[8] DOI: 10.1090/S0002-9947-00-02506-X · Zbl 1029.20018
[9] Büchi J. R., Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 34 pp 337–
[10] Cartier P., Lecture Notes in Mathematics 85, in: Problèmes Combinatoires de Commutation et Réarrangements (1969) · Zbl 0186.30101
[11] DOI: 10.1016/j.ic.2005.04.002 · Zbl 1101.68649
[12] DOI: 10.1142/S0218196702000870 · Zbl 1007.03008
[13] DOI: 10.1007/s00224-003-1110-x · Zbl 1067.03017
[14] DOI: 10.1016/S0304-3975(98)00313-2 · Zbl 0930.68074
[15] DOI: 10.1142/S0218196706003372 · Zbl 1112.03009
[16] DOI: 10.1142/9789814261456
[17] DOI: 10.1016/0021-8693(87)90010-X · Zbl 0692.05035
[18] Durnev V. G., Sibirsky Matematicheskie Jurnal 36 pp 1067–
[19] Epstein D. B. A., Word Processing in Groups (1992)
[20] Feferman S., Fund. Math. 47 pp 57–
[21] DOI: 10.1007/s00233-006-0602-9 · Zbl 1124.20040
[22] DOI: 10.1006/jabr.1995.1010 · Zbl 0831.20032
[23] DOI: 10.1017/CBO9780511551574
[24] Jantzen M., EATCS Monographs on Theoretical Computer Science 14 (1988)
[25] DOI: 10.1142/S0218196707003330 · Zbl 1184.20031
[26] DOI: 10.1016/j.jalgebra.2006.03.033 · Zbl 1110.03020
[27] DOI: 10.1142/S0218196706003001 · Zbl 1151.03003
[28] DOI: 10.1142/S021819670200122X · Zbl 1044.20024
[29] DOI: 10.1007/978-3-642-61896-3
[30] Makanin G. S., Math. Sbornik 103 pp 147–
[31] Makanin G. S., Izv. Akad. Nauk SSR, Ser. Math. 46 pp 1199–
[32] Makanin G. S., Izv. Akad. Nauk SSSR, Ser. Mat. 48 pp 735–
[33] Marchenkov S. S., Sibirsky Matematicheskie Jurnal 23 pp 196–
[34] DOI: 10.2140/pjm.1964.14.1343 · Zbl 0144.01201
[35] Meier J., Geometriae Dedicata 61 pp 29–
[36] Merzlyakov Y. I., Algebra i Logika Sem. 5 pp 25–
[37] DOI: 10.1016/0020-0190(88)90049-X · Zbl 0653.03026
[38] DOI: 10.2307/1968867 · Zbl 0060.12501
[39] Ochmański E., Bull. Eur. Assoc. Theoret. Comput. Sci. (EATCS) 27 pp 56–
[40] Papadimitriou C. H., Computational Complexity (1994) · Zbl 0833.68049
[41] DOI: 10.1145/990308.990312 · Zbl 1192.68372
[42] M. Presburger, Comptes Rendus du Premier Congrès des Mathématicienes des Pays Slaves (Warsaw, 1929) pp. 92–101.
[43] DOI: 10.2307/2268308 · Zbl 0063.06362
[44] Repin N. N., Voprosy Kibernetiki (Moskva) 134 pp 167–
[45] DOI: 10.1007/BF01241140 · Zbl 0845.57002
[46] DOI: 10.1007/BF00970391 · Zbl 0452.20057
[47] DOI: 10.1007/BF00969107 · Zbl 0595.03006
[48] DOI: 10.1016/0304-3975(87)90080-6 · Zbl 0634.68076
[49] K. U. Schulz, Word Equations and Related Topics, Lecture Notes in Computer Science 572, ed. K. U. Schulz (Springer, 1991) pp. 85–150.
[50] Semenov A. L., Soviet Math. Dokl. 21 pp 952–
[51] DOI: 10.1070/SM1983v044n01ABEH000954 · Zbl 0497.20046
[52] DOI: 10.1007/s002330010075 · Zbl 0992.20042
[53] DOI: 10.1051/ita:2001103 · Zbl 1019.20028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.