Slava's Monoid Zoo
a day ago
- #monoid presentation
- #word problem
- #Knuth-Bendix completion
- The word problem for finitely-presented monoids is undecidable in general; even short presentations can be undecidable.
- Knuth-Bendix completion may fail by running forever or if the monoid has an undecidable word problem.
- Craig C. Squier showed that some monoids with decidable word problems lack finite complete rewriting systems, using monoid S1 as an example.
- Search for 'smallest' monoid presentations unsolvable by Knuth-Bendix completion is ongoing, involving techniques like morphocompletion and enumeration.
- Enumeration of one-relation monoids with length ≤10 reveals exceptions; it's unknown if all such monoids have finite complete rewriting systems.
- Research by teams like James D. Mitchell's uses various methods to solve word problems in one-relation monoids beyond finite complete rewriting systems.
- Specific examples, such as ⟨a, b | abbab=baabb⟩ and ⟨a, b | bababbbabba=a⟩, have been studied; some admit finite complete rewriting systems with added generators.
- Unknown cases like {baabbbaba ↔ a} and {baaabaaa ↔ aba} are being explored, with some solvable via finite complete rewriting systems after generator expansion.