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

DOI10.1007/s00233-010-9288-0zbMath1228.20044arXiv1012.3547MaRDI 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

semigroups; word problem; linear time algorithms; braid monoids; finite complete rewriting systems; conjugacy problems; string rewriting systems

Mathematics Subject Classification ID

20F05: Generators, relations, and presentations of groups

20M05: Free semigroups, generators and relations, word problems

20F36: Braid groups; Artin groups

68Q42: Grammars and rewriting systems

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

Related Items

Confluence of algebraic rewriting systems, Conjugacy relations of prefix codes

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