×

zbMATH — the first resource for mathematics

On deciding whether a monoid is a free monoid or is a group. (English) Zbl 0592.20059
Monoids which are described by a given finite presentation (\(\Sigma\) ;R), i.e. \(\Sigma\) is a finite alphabet and R is a finite string-rewriting system on \(\Sigma\), are considered. It is shown that the problem whether or not such a monoid is a free one or a group are undecidable in general. However it is shown that both these problems are effectively reducible to a very restricted form of the uniform word problem. So whenever for some class of presentations this restricted form of the uniform word problem is decidable then the above decision problems become decidable. It is proved that this holds in particular for the class of all presentations involving finite complete string-rewriting systems.
Reviewer: V.Fleischer

MSC:
20M05 Free semigroups, generators and relations, word problems
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20F05 Generators, relations, and presentations of groups
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Book, R.V.: When is a monoid a group? The Church-Rosser case is tractable. Theor. Comput. Sci. 18, 325–331 (1982) · Zbl 0489.68021 · doi:10.1016/0304-3975(82)90072-X
[2] Book, R.V.: Decidable sentences of Church-Rosser congruences. Theor. Comput. Sci. 24, 301–312 (1983) · Zbl 0525.68015 · doi:10.1016/0304-3975(83)90005-1
[3] Book, R.V.: Thue systems as rewriting systems. In: Rewriting techniques and applications. (J.P. Jouannaud, ed). Lect. Notes Comput. Sci. 202, pp. 63–94. Berlin, Heidelberg, New York: Springer 1985 · Zbl 0587.03026
[4] Lallement, G.: Semigroups and combinatorial applications. New York, Chichester, Brisbane, Toronto: John Wiley 1979 · Zbl 0421.20025
[5] Magnus, W., Karrass, A., Solitar, D.: Combinatorial group theory, 2nd. rev. ed., New York: Dover 1976 · Zbl 0362.20023
[6] Markov, A.A.: Impossibility of algorithms for recognizing some properties of associative systems. Dokl. Akad. Nauk SSSR 77, 953–956 (1951)
[7] Mostowski, A.: (Review of Reference 6) J. Symb. Logic 17, 151–152 (1952) · doi:10.2307/2266280
[8] Narendran, P., Otto, F.: Complexity results on the conjugacy problem for monoids. Theor. Comput. Sci. 35, 227–243 (1985) · Zbl 0588.03022 · doi:10.1016/0304-3975(85)90016-7
[9] Otto, F.: Some undecidability results for non-monadic Church-Rosser Thue systems. Theor. Comput. Sci. 33, 261–278 (1984) · Zbl 0563.03019 · doi:10.1016/0304-3975(84)90090-2
[10] Otto, F.: Church-Rosser Thue systems that present free monoids. SIAM J. Comput. (To appear) · Zbl 0599.20091
[11] Tietze, H.: Über die topologischen Invarianten mehrdimensionaler Mannigfaltigkeiten. Monatsh. Math. Phys. 19, 1–118 (1908) · JFM 39.0720.05 · doi:10.1007/BF01736688
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.