The Knuth-Bendix algorithm and the conjugacy problem in monoids. (Q633198): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 09:19, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The Knuth-Bendix algorithm and the conjugacy problem in monoids. |
scientific article |
Statements
The Knuth-Bendix algorithm and the conjugacy problem in monoids. (English)
0 references
31 March 2011
0 references
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.
0 references
string rewriting systems
0 references
word problem
0 references
linear time algorithms
0 references
finite complete rewriting systems
0 references
conjugacy problems
0 references
braid monoids
0 references
semigroups
0 references