Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group

DOI10.1016/0304-3975(84)90044-6zbMath0555.20036OpenAlexW2016799182MaRDI QIDQ760506

Friedrich Otto

Publication date: 1984

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(84)90044-6

zbMATH Keywords

presentationword problempolynomial-time algorithmfinite complete rewriting systemGreendlinger groupJantzen monoidKnuth- Bendix ordering

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Free semigroups, generators and relations, word problems (20M05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (9)

Thue systems as rewriting systems ⋮ Analysis of Dehn's algorithm by critical pairs ⋮ About the descriptive power of certain classes of finite string-rewriting systems ⋮ Commutativity in groups presented by finite Church-Rosser Thue systems ⋮ The word problem for one-relation monoids: a survey ⋮ Finite complete rewriting systems for groups ⋮ Finite complete rewriting systems and the complexity of word problem ⋮ A note on a special one-rule semi-Thue system ⋮ A finite Thue system with decidable word problem and without equivalent finite canonical system

Cites Work

• Orderings for term-rewriting systems
• Remarks on an example of Jantzen
• The undecidability of the preperfectness of Thue systems
• A note on representations of a certain monoid
• Testing for the Church-Rosser property
• On a special monoid with a single defining relation
• When is a monoid a group? The Church-Rosser case is tractable
• Subrekursive Komplexität bei Gruppen. I: Gruppen mit vorgeschriebener Komplexität
• Dehn's algorithm for the word problem
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Confluent and Other Types of Thue Systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group