The Knuth-Bendix algorithm and the conjugacy problem in monoids. (Q633198): Difference between revisions

In the last almost 20 years, string-rewriting systems have taken so much interest both from Theoretical Computer Science and Mathematics. In particular, finite and complete (Noetherian and confluent) string-rewriting systems have been used to solve the \textit{word problem} which is one of the decision problems. After that, a question naturally arises which asks whether the use of rewriting systems can be an efficient tool for solving the conjugacy problem. In this paper, the author studies this subject and uses rewriting systems in order to solve the conjugacy problems (LConj, RConj, Conj, Trans) in some semigroups and monoids. The conjugacy problem studied in here, Trans, is the same with the first conjugacy notion studied by \textit{G. Kudryavtseva} and \textit{V. Mazorchuk} [Semigroup Forum 78, No. 1, 14-20 (2009; Zbl 1171.20035)]. The author also extends the classical theory of rewriting developed by Knuth and Bendix to a rewriting that takes into account the cyclic conjugates. At this point I should remind that some geometric aspects (graphs, (left or right) Adyan graphs, pictures etc.) have been also used to solve conjugacy problems in the literature.