The Knuth-Bendix algorithm and the conjugacy problem in monoids.

DOI10.1007/S00233-010-9288-0MaRDI QIDQ633198zbMATH OpenOpenAlexFDO

Authors Fabienne Chouraqui

Publication date 31 March 2011

Published in Semigroup Forum (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.3547

zbMATH Keywords

braid monoidsconjugacy problemsfinite complete rewriting systemslinear time algorithmssemigroupsstring rewriting systemsword problem

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Braid groups; Artin groups (20F36) Free semigroups, generators and relations, word problems (20M05) Grammars and rewriting systems (68Q42)

Abstract: We present an algorithmic approach to the conjugacy problems in monoids, using rewriting systems. We extend the classical theory of rewriting developed by Knuth and Bendix to a rewriting that takes into account the cyclic conjugates.

Review text

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.

Recommendations

• Decidability and independence of conjugacy problems in finitely presented monoids
• Four notions of conjugacy for abstract semigroups
• Cyclic rewriting and conjugacy problems.
• On deciding the confluence of a finite string-rewriting system on a given congruence class
• Deciding conjugacy in Sylvester monoids and other homogeneous monoids.
• scientific article; zbMATH DE number 2074997
• scientific article; zbMATH DE number 1008515
• scientific article; zbMATH DE number 42096
• scientific article; zbMATH DE number 176741
• scientific article; zbMATH DE number 3871338

Cites work

• Artin groups, rewriting systems and three-manifolds
• Complexity results on the conjugacy problem for monoids
• Confluent and Other Types of Thue Systems
• CONJUGACY AND TRANSPOSITION FOR INVERSE MONOID PRESENTATIONS
• CONJUGACY IN FREE INVERSE MONOIDS
• Conjugacy in monoids with a special Church-Rosser presentation is decidable
• Conjugacy in special monoids
• Equidivisible semigroups
• scientific article; zbMATH DE number 47903 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• REWRITING SYSTEMS IN ALTERNATING KNOT GROUPS
• Term rewriting for the conjugacy problem and the braid groups
• The problems of cyclic equality and conjugacy for finite complete rewriting systems

Cited in

(5)

• Complexity results on the conjugacy problem for monoids
• Term rewriting for the conjugacy problem and the braid groups
• Cyclic rewriting and conjugacy problems.
• Conjugacy relations of prefix codes
• Confluence of algebraic rewriting systems

This page was built for publication: The Knuth-Bendix algorithm and the conjugacy problem in monoids.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q633198)