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

DOI10.1007/s00233-010-9288-0zbMath1228.20044arXiv1012.3547OpenAlexW2146326601MaRDI QIDQ633198

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) Free semigroups, generators and relations, word problems (20M05) Braid groups; Artin groups (20F36) Grammars and rewriting systems (68Q42) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items

Conjugacy relations of prefix codes, Confluence of algebraic rewriting systems

Cites Work

• Unnamed Item
• Unnamed Item
• Conjugacy in monoids with a special Church-Rosser presentation is decidable
• Complexity results on the conjugacy problem for monoids
• The problems of cyclic equality and conjugacy for finite complete rewriting systems
• Conjugacy in special monoids
• Artin groups, rewriting systems and three-manifolds
• Term rewriting for the conjugacy problem and the braid groups
• Equidivisible semigroups
• CONJUGACY IN FREE INVERSE MONOIDS
• Confluent and Other Types of Thue Systems
• CONJUGACY AND TRANSPOSITION FOR INVERSE MONOID PRESENTATIONS
• REWRITING SYSTEMS IN ALTERNATING KNOT GROUPS