×

zbMATH — the first resource for mathematics

Conjugacy in monoids with a special Church-Rosser presentation is decidable. (English) Zbl 0551.20044
The paper concerns conjugacy relations on monoids. Direct generalizations introduced for free monoids to an arbitrary monoid are not equivalence relations. For this reason, the author proposes three other definitions of conjugacy for arbitrary monoids. A chain of inclusions of all five conjugacy relations is shown. All these relations coincide for free monoids, for monoids which are groups, and for monoids presented by special Church-Rosser Thue systems.
It is shown, that for finitely presented monoids, the word problem and the conjugacy problem are independent, and that there exists a monoid presented by a finite special Thue system such that the conjugacy problem for this monoid is undecidable.
In the main result of the paper, the author proves that the conjugacy problem for monoids presented by a finite special Church-Rosser Thue system is decidable. It remains open whether the Church-Rosser property of the Thue system is sufficient for decidability of the conjugacy problem of a monoid.
Reviewer: J.Bergandy

MSC:
20M05 Free semigroups, generators and relations, word problems
03D03 Thue and Post systems, etc.
20M15 Mappings of semigroups
20M35 Semigroups in automata theory, linguistics, etc.
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] Adjan, S. I.,Defining relations and algorithmic problems for groups and semigroups, Proc. Steklov Inst. math. 85 (1966), American Math. Soc., 1967.
[2] Book, R. V.,Confluent, and other types of thue systems, J. Assoc. Comput. Mach. 29 (1982), 171–182. · Zbl 0478.68032
[3] Book, R. V.,Decidable sentences of Church-Rosser congruences, Theoret. Comput. Sci. 24 (1983), to appear. · Zbl 0525.68015
[4] Book, R. V., M. Jantzen and C. Wrathall,Monadic Thue systems, Theoret. Comput. Sci. 19 (1982), 231–251. · Zbl 0488.03020 · doi:10.1016/0304-3975(82)90036-6
[5] Boone, W. W.,Certain simple unsolvable problems of group theory, I, II, III, IV, V, VI, Nederl. Akad. Wetensch. Proc. Ser. A 57 (1954), 231–237, 492–497, 58 (1955), 252–256, 571–577, 60 (1957), 22–27, 227–232.
[6] Cochet, Y.,Church-Rosser congruences on free semigroups, Colloq. Math. Soc. Janos Bolgai: Algebraic Theory of Semigroups 20 (1976), 51–60.
[7] Collins, D. J.,Recrsively enumerable degrees and the conjugacy problem, Acta Math. 122 (1969), 115–160. · Zbl 0175.27501 · doi:10.1007/BF02392008
[8] Lallement, G.,On monoids presented by a single relations, J. Algebra 32 (1974), 370–388. · Zbl 0307.20034 · doi:10.1016/0021-8693(74)90146-X
[9] Lallement, G.,Semigroups and Combinatorial Applications, Wiley-Interscience, 1979. · Zbl 0421.20025
[10] Magnus, W., A. Karrass, and D. Solitar,Combinatorial Group Theory (2nd revised ed.), Dover, 1976. · Zbl 0362.20023
[11] Markov, A. A.,On the impossibility of certain algorithms in the theory of associative systems, Dokl. Akad. Nauk 55 (1947), 587–590, 58 (1947), 353–356.
[12] Post, E. L.,Recursive unsolvability of a problem of Thue, J. Symbolic Logic 12 (1947), 1–11. · Zbl 1263.03030 · doi:10.2307/2267170
[13] Squier, C.,The group of units of a monoid with a Church-Rosser presentation, in preparation.
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.