×

zbMATH — the first resource for mathematics

Solvability of equations in graph groups is decidable. (English) Zbl 1112.03009

MSC:
03B25 Decidability of theories and sets of sentences
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20M05 Free semigroups, generators and relations, word problems
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX Cite
Full Text: DOI
References:
[1] DOI: 10.1007/BF00993053 · Zbl 0423.68027
[2] DOI: 10.1007/BF01917515
[3] Benois M., C. R. Acad. Sci. Paris, Sér. A 269 pp 1188–
[4] DOI: 10.1090/S0002-9947-00-02506-X · Zbl 1029.20018
[5] Cartier P., Lecture Notes in Mathematics 85, in: Problèmes Combinatoires de Commutation et Réarrangements (1969) · Zbl 0186.30101
[6] DOI: 10.1007/s00224-003-1110-x · Zbl 1067.03017
[7] DOI: 10.1016/S0304-3975(98)00313-2 · Zbl 0930.68074
[8] DOI: 10.1142/9789814261456
[9] DOI: 10.1090/S0002-9939-1987-0891135-1
[10] DOI: 10.1145/321765.321782 · Zbl 0273.68011
[11] DOI: 10.1016/S0304-3975(96)00321-0 · Zbl 0908.68107
[12] Makanin G. S., Math. Sbornik 103 pp 147–
[13] Makanin G. S., Izv. Akad. Nauk SSR, Ser. Math. 46 pp 1199–
[14] A. Mazurkiewicz, Petri Nets, Applications and Relationship to Other Models of Concurrency, Lecture Notes in Computer Science 255, eds. W. Brauer (Springer-Verlag, Berlin Heidelberg, 1987) pp. 279–324.
[15] Ochmański E., Bull. Eur. Assoc. Theoret. Comput. Sci. (EATCS) 27 pp 56–
[16] DOI: 10.1142/9789814261456_0006
[17] DOI: 10.1145/990308.990312 · Zbl 1192.68372
[18] Schaefer M., J. Comput. Syst. Sci. pp 365–
[19] K. U. Schulz, Word Equations and Related Topics, Lecture Notes in Computer Science 572, ed. K. U. Schulz (Springer-Verlag, Berlin, Heidelberg, 1991) pp. 85–150.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.