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

semigroupsword problemlinear time algorithmsbraid monoidsfinite complete rewriting systemsconjugacy problemsstring rewriting systems

Mathematics Subject Classification ID

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

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.

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

• scientific article; zbMATH DE number 47903 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• Artin groups, rewriting systems and three-manifolds
• CONJUGACY AND TRANSPOSITION FOR INVERSE MONOID PRESENTATIONS
• CONJUGACY IN FREE INVERSE MONOIDS
• Complexity results on the conjugacy problem for monoids
• Confluent and Other Types of Thue Systems
• Conjugacy in monoids with a special Church-Rosser presentation is decidable
• Conjugacy in special monoids
• Equidivisible semigroups
• 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)

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

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)