Return to my home page.

---

My interest in finitely-presented monoids stems from the Swift compiler's use of the Knuth-Bendix completion algorithm to implement same-type requirements. There are multiple possible formulations of the Knuth-Bendix algorithm, but in Swift's case, we're using it to solve the word problem in a finitely-presented monoid.

In the Swift compiler, the finitely-presented monoids are the generic signatures of function and type declarations, and the relations in each monoid correspond to the generic requirements imposed upon that declaration. This is all documented in Chapters 16--18 of Compiling Swift Generics, if you're curious.

The word problem

The word problem asks the yes/no question of whether two words over a finite alphabet are equivalent under a given set of bidirectional string rewriting rules, or "relations". Here is an example. Suppose you're given these two relations:

1. 🍌🍎🍌 = 🍎🍎🍎
2. 🍌🍌🍌 = 🍌🍌

Can you see a way to transform a string of 8 apples "🍎🍎🍎🍎🍎🍎🍎🍎" into a string of 10 apples "🍎🍎🍎🍎🍎🍎🍎🍎🍎🍎"?

It is not at all obvious that this can be done, and in fact it takes a minimum of 15 steps. (You can discover the solution for yourself by playing this simple game.) This is a concrete instance of the word problem: we have two words a⁸ and a¹⁰, and the monoid presentation ⟨a, b | bab=aaa, bbb=bb⟩, and we want to know if the two words are equivalent with respect to those two rules.

Even though the above presentation is very short, the word problem here is already quite difficult. A classic result is that the word problem for finitely-presented monoids is undecidable in the general case. A very short example of a monoid with an undecidable word problem appears in the paper An associative calculus with an insoluble problem of equivalence (for an English translation with commentary, see G. S. Tseytin's seven-relation semigroup with undecidable word problem):

⟨a, b, c, d, e | ac=ca, ad=da, bc=cb, bd=db, eca=ce, edb=de, cca=ccae⟩

Finite complete rewriting systems

Knuth-Bendix attempts to construct a finite complete rewriting system from the bidirectional equivalences that define the monoid. A finite complete rewriting system is a set of directed reduction rules which allows us to reduce any word into a normal form in a finite number of steps. This completely solves the word problem for the original monoid: given any pair of words, we can first reduce both words to their normal form by applying the reduction rules in our FCRS, and then we check if we get identical normal forms.

Knuth-Bendix completion will sometimes fail; the failure mode is that it runs forever, continuing to add new rules which never converge. At the very least, Knuth-Bendix must fail if the given input rules define a monoid with an undecidable word problem. Undecidable instances aside, one might then ask: if our monoid has a decidable word problem, can we still solve the word problem with an FCRS? This was answered in the negative by Craig C. Squier in the late 1980's. In a paper titled A finiteness condition for rewriting systems, Squier considered the monoid S₁, with five generators and five relations:

S₁ := ⟨a, b, t, x, y | ab=1, xa=atx, xt=tx, xb=bx, xy=1⟩

Squier shows that this monoid does not have finite derivation type, which is a necessary condition for the existence of an FCRS presenting the same monoid. Thus, Knuth-Bendix completion will fail with any presentation of this monoid, not just the one given above, no matter what generating set or reduction order we choose. Despite that, S₁ happens to have a decidable word problem. An even shorter example, with three generators and three relations, appears in a paper titled On finite complete rewriting systems, finite derivation type, and automaticity for homogeneous monoids:

⟨a, b, c | ac=ca, bc=cb, cab=cbb⟩

The above monoid again has a decidable word problem (the relations preserve the length of the word, so we can decide if two words are equivalent by first comparing their lengths, followed by an exhaustive enumeration if both words have equal length); just not by Knuth-Bendix completion.

The goal of this investigation

The above examples serve as motivation for my investigation, which can be summarized as follows:

Goal: To find, in some subjective sense, the "smallest" or "shortest" monoid presentations whose whose word problem cannot be solved by a finite complete rewriting system (in practical terms, applying some variant of Knuth-Bendix completion).

To search for a finite complete rewriting system that presents a monoid, I use a variation of the technique described in Morphocompletion for one-relation monoids, to introduce new generators to the presentation; I then attempt completion with a variety of reduction orders simultaneously:

• Shortlex for all permutations of the alphabet
• Recursive path for all permutations of the alphabet together with all possible distinct degree assignments

Besides solving the word problem, an FCRS tells you if the presented monoid has a finite number of elements (distinct equivalence classes of strings), in which case it is possible to enumerate the elements, and construct a Cayley table and Cayley graph for the monoid. It is also decidable if an FCRS presents a group, in which case the inverses of the generators can be determined as well. My side quest has been to collect and analyze this data about short presentations, which you can find in the data sets below.

To answer the one final question you may have:

Why? Because it's an interesting problem.

---

The data set

I can find a finite complete rewriting system for every two-generated two-relation monoid with sum of sides ≤ 11, with 24 exceptions that are listed on the page below.

Explore:

A fair number of instances in the enumeration "collapse" in various trivial ways:

• ⟨a, b | aa=a, ab=1⟩ is the first presentation of the trivial group with one element, but there are 2030 more.
• ⟨a, b | aa=1, ab=1⟩ is the first presentation of the group with two elements, but there are 1990 more.
• ⟨a, b | aa=a, aaa=b⟩ is the other possible monoid structure with two elements; not nearly as popular, with only 46 other duplicates in the enumeration.

This enumeration also includes some nice short presentations of various classic finite groups:

• ⟨a, b | abba=b, baba=1⟩ is a presentation of the symmetric group of degree 3, with 6 elements. (An interesting fact is that while this is the only non-Abelian group of order 6 up to isomorphism, there are many more monoids that are not groups, for example the slightly ridiculous ⟨a, b | ab=a, bbbb=ba⟩.)
• ⟨a, b | aba=b, aabb=1⟩ is a presentation of the Quaternion group with 8 elements. Can you see which elements can work as i, j, k, and -1? (There are multiple possible assignments, of course.)
• ⟨a, b | aaa=1, abba=b⟩ is a finite monoid with 27 elements, but the group with the same presentation is SL(2, 3). (The monoid has three more elements, the powers of a.)

⟨a, b | aaa=a, abba=bb⟩

My main result so far is that ⟨a, b | aaa=a, abba=bb⟩ is the unique two generator, two relation monoid with length 10 that cannot be presented by a finite complete rewriting system over any alphabet (the monoid is "not FCRS"). In fact, just like Squier's S₁, it does not have finite derivation type.

Read the proof:

Note that the article describes an earlier enumeration of two-relation monoids up to length 10; at the time, this monoid was one of three "hard" instances. Since then, I've found an FCRS for the other two:

⟨a, b | aba=aa, baa=aab⟩

I also have an earlier result that one of the length 11 hard instances is not FCRS. The main proof fits in two pages, and it is (relatively speaking) quite straightforward, relying only on nothing more than the preliminary definitions and the pumping lemma for regular languages. I would be very happy if this was incorporated as an example in someone's textbook on string rewriting or Knuth-Bendix completion!

Read the proof:

An interesting question (I do not know the answer) is if this monoid also fails to have finite derivation type.

Resolving the status of the remaining length 11 hard instances in the two relation enumeration is still an open problem. (A very observant reader might notice that the "8 apples" monoid from the introduction, ⟨a, b | bab=aaa, bbb=bb⟩, appears among them. I'm pretty sure it's not FCRS.) Let me know if you figure anything out!

---

I've also investigated monoids with one defining relation.

The data set

I can find a finite complete rewriting system for every two-generated one-relation monoid with sum of sides ≤ 10, with five exceptions that are listed at the page below. It is not known if every one-relation monoid can be presented by a finite complete rewriting system. Maybe it is too much to hope for, but if the answer is "no", perhaps one of these will be the first such counterexample!

Explore:

A number of classical one-relation monoids can be found in this enumeration:

• ⟨a, b | ab=1⟩ is the bicyclic monoid.
• ⟨a, b | aba=1⟩ is the Abelian group of integers under addition. (Can you see why ba=ab, and what the integer values of a and b must be?)
• ⟨a, b | bab=aba⟩ is the submonoid of positive words in the Braid group B₃, discussed in A finite Thue system with decidable word problem and without equivalent finite canonical system. It has no FCRS over the alphabet {a, b}, but if you extend the alphabet with one auxiliary generator equivalent to one of ab, ba, or aba, you can obtain an FCRS.
• ⟨a, b | abbaab=1⟩ is anti-isomorphic to the Jantzen monoid, discussed in Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group. To obtain an FCRS for this monoid (which is incidentally a group), one must not only expand the generating set, but also use a recursive path order which allows for length-increasing rewrite rules.

There are no finite monoids in this enumeration, because it takes at least two relations to present a finite monoid with two generators. A team led by James D. Mitchell at University of St Andrews has been looking at solving the word problem in one relation monoids using a variety of techniques, not just FCRS, with a larger enumeration than mine---they're enumerating all ⟨a, b | u=v⟩ where |u| ≤ 10 and |v| ≤ 10, not just |u|+|v| ≤ 10. Check out their publications:

Minor results

I've found finite complete rewriting systems for a handful of one relation monoids that have stumped others, which is perhaps mildly interesting. You can see the slightly absurd phenomenon in action here, where even though we're starting from a single relation, we might get a finite complete rewriting system with a large number of rules.

(1) The below monoid, due to Victor Maltcev, appears as Exercise 4.10:8 (ii) in An invitation to General Algebra and Universal Constructions by George M. Bergman:

(ii) (Victor Maltcev) Does there exist a normal form or other useful description for the monoid presented by generators a, b and the relation abbab = baabb ? (I do not know the answer.)

The monoid ⟨a, b | abbab=baabb⟩ is anti-isomorphic to ⟨a, b | abaab=aabba⟩, which admits a finite complete rewriting system.

(2) The next example appears in the fantastic survey of The Word Problem for One-Relation Monoids by C.F. Brodda, where he writes:

We note in passing that the smallest monadic one-relation monoid to which no result in the literature appears to be available to solve the word problem for is ⟨a, b | bababbbabba=a⟩. The author has not found a finite complete rewriting system for this monoid, but has solved the word problem for this monoid by other means.

The presentation ⟨a, b | bababbbabba=a⟩ does not appear in my enumeration, for it has length 12. It has the following finite complete rewriting system, once we add a letter c=bba:

1. ca ⇒ ac
2. b²a ⇒ c
3. cbac ⇒ abc²
4. cbabc² ⇒ ba
5. ba² ⇒ (ab)²c³
6. (ba)²c ⇒ aba(bc²)²
7. b(ab)²c² ⇒ a
8. c(ba)² ⇒ abcba
9. cbabcba ⇒ a
10. (ba)³ ⇒ (ab)²c(cb)²a
11. b(ab)²cba ⇒ (ab)²c²

(3) In the paper On the Dehn functions of a class of monadic one-relation monoids, the same author defines this family of monoids:

Π_N := ⟨a,b | baa(ba)^N=a⟩

He then asks:

Question 3. Does Π_N admit a finite complete rewriting system for all N ≥ 2?

I believe they all admit finite complete rewriting systems. Here is N=2, ⟨a, b | baababa=a⟩:

1. cac³ ⇒ ac
2. cac²a ⇒ a²
3. a²c³ ⇒ c(ac)²
4. a²c²a ⇒ caca²
5. ad ⇒ ca
6. dc³ ⇒ c
7. dc²a ⇒ a
8. dac ⇒ ac⁵
9. dcac ⇒ ac³
10. da² ⇒ ac⁴a
11. dca² ⇒ ac²a
12. ab ⇒ c
13. bc ⇒ db
14. ba ⇒ d

And N=3, ⟨a, b | baabababa=a⟩:

1. cac⁵ ⇒ ac
2. cac⁴a ⇒ a²
3. a²c⁵ ⇒ cac³ac
4. a²c⁴a ⇒ cac³a²
5. ad ⇒ ca
6. dc⁵ ⇒ c
7. dc⁴a ⇒ a
8. dac ⇒ ac¹⁷
9. dcac ⇒ ac¹³
10. dc²ac ⇒ ac⁹
11. dc³ac ⇒ ac⁵
12. da² ⇒ ac¹⁶a
13. dca² ⇒ ac¹²a
14. dc²a² ⇒ ac⁸a
15. dc³a² ⇒ ac⁴a
16. ab ⇒ c
17. bc ⇒ db
18. ba ⇒ d

And N=4, ⟨a, b | baababababa=a⟩:

1. cac⁶ ⇒ ac
2. cac⁵a ⇒ a²
3. a²c⁶ ⇒ cac⁴ac
4. a²c⁵a ⇒ cac⁴a²
5. ad ⇒ ca
6. dc⁶ ⇒ c
7. dc⁵a ⇒ a
8. dac ⇒ ac²⁶
9. dcac ⇒ ac²¹
10. dc²ac ⇒ ac¹⁶
11. dc³ac ⇒ ac¹¹
12. dc⁴ac ⇒ ac⁶
13. da² ⇒ ac²⁵a
14. dca² ⇒ ac²⁰a
15. dc²a² ⇒ ac¹⁵a
16. dc³a² ⇒ ac¹⁰a
17. dc⁴a² ⇒ ac⁵a
18. ab ⇒ c
19. bc ⇒ db
20. ba ⇒ d

This pattern continues for N=5, 6, 7, ... as well, and you seem to always get an FCRS by adding two generators c=ab and d=ba.

(4) The next example is from a talk titled Off with the head! Termination provers and the word problem for 1-relation monoids by Reinis Cirpons:

The 1-relation Thue systems for which the decidability of the word problem is unknown to us: {baabbbaba ↔ a} {baaabaaa ↔ aba}.

The first one is anti-isomorphic to ⟨a, b | ababbbaab=a⟩, which is FCRS. The second one ⟨a, b | baaabaaa=aba⟩ has length 11 so it does not appear in my enumeration, but it can also be solved by FCRS if we add c=aaaba and d=abaaa:

1. bc³ ⇒ dbd
2. bc²ad ⇒ dba
3. abd ⇒ bcad
4. ac ⇒ cad
5. abc ⇒ dba
6. dbcadc ⇒ adbd
7. cbcadc ⇒ ad²bd
8. adbc ⇒ cba
9. ab²cd² ⇒ bcdbad²
10. ab²c² ⇒ bcdbcad
11. ab²cdc ⇒ bcdbadc
12. ab²cdbc ⇒ bcdbcba
13. aba ⇒ bca²
14. a²d ⇒ ca²
15. dbc(ad)² ⇒ adba
16. cbc(ad)² ⇒ ad²ba
17. ab²cad ⇒ bcdbca²
18. ab²cdad ⇒ bcdb(ad)²
19. adbad² ⇒ cbda²
20. ab²cdbad² ⇒ bcdbcbda²
21. adbadc ⇒ cbd(ad)²
22. ab²cdbadc ⇒ bcdbcbd(ad)²
23. ab²ca² ⇒ bcdba³
24. adb(ad)² ⇒ cbdada²
25. ab²cdb(ad)² ⇒ bcdbcbdada²
26. bca⁴ ⇒ d
27. adba³ ⇒ c
28. ab²cdba³ ⇒ bcdbc
29. dba⁵ ⇒ ad
30. cba⁵ ⇒ ad²