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

DOI10.1016/0304-3975(84)90044-6MaRDI QIDQ760506zbMATH OpenOpenAlexFDO

Authors 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

presentationpolynomial-time algorithmword problemfinite complete rewriting systemGreendlinger groupJantzen monoidKnuth- Bendix ordering

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) Free semigroups, generators and relations, word problems (20M05)

Recommendations

• Finite complete rewriting systems for groups
• scientific article; zbMATH DE number 2074997
• Geodesic rewriting systems and pregroups
• Complete rewriting system for the Schützenberger product of \(n\) groups
• Remarks on an example of Jantzen

Cites work

• scientific article; zbMATH DE number 3850463 (Why is no real title available?)
• scientific article; zbMATH DE number 3861446 (Why is no real title available?)
• scientific article; zbMATH DE number 3817023 (Why is no real title available?)
• scientific article; zbMATH DE number 4005606 (Why is no real title available?)
• scientific article; zbMATH DE number 3654376 (Why is no real title available?)
• scientific article; zbMATH DE number 3528212 (Why is no real title available?)
• scientific article; zbMATH DE number 3563392 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 3299786 (Why is no real title available?)
• A note on representations of a certain monoid
• Algebraic simplification
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Confluent and Other Types of Thue Systems
• Dehn's algorithm for the word problem
• On a special monoid with a single defining relation
• Orderings for term-rewriting systems
• Remarks on an example of Jantzen
• Subrekursive Komplexität bei Gruppen. I: Gruppen mit vorgeschriebener Komplexität
• Testing for the Church-Rosser property
• The undecidability of the preperfectness of Thue systems
• When is a monoid a group? The Church-Rosser case is tractable

Cited in

(13)

• Thue systems as rewriting systems
• Analysis of Dehn's algorithm by critical pairs
• Finite complete rewriting systems for regular semigroups.
• On groups presented by monadic rewriting systems with generators of finite order.
• Commutativity in groups presented by finite Church-Rosser Thue systems
• Finite complete rewriting systems for groups
• A note on a special one-rule semi-Thue system
• Finite complete rewriting systems and the complexity of word problem
• A finite Thue system with decidable word problem and without equivalent finite canonical system
• Complete rewriting system for the Schützenberger product of \(n\) groups
• Remarks on an example of Jantzen
• The word problem for one-relation monoids: a survey
• About the descriptive power of certain classes of finite string-rewriting systems

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

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