⟨ Slava's | Monoid Zoo ⟩

Contents

• Background
  • The word problem
  • Finite complete rewriting systems
• The goal of this investigation
• Two generators, two relations
  • The enumeration
  • ⟨a, b | aaa=a, abba=bb⟩
  • ⟨a, b | aba=aa, baa=aab⟩
  • Finite monoids
• Two generators, one relation
  • The enumeration
  • Related work
  • Minor results

Background

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

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

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 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⟩

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

The goal of this investigation

Goal: To find, in some subjective sense, the "smallest" or "shortest" monoid presentation(s) whose whose word problem cannot be solved by a finite complete rewriting system.

Similarly, you can imagine enumerating all monoid presentations in a certain order, and trying to find a finite complete rewriting system for each one. To construct an FCRS, I first attempt a variation of the technique described in Morphocompletion for one-relation monoids, which adds new new generators to the presentation before performing Knuth-Bendix completion algorithm 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, various properties of the presented monoid can be decided from an FCRS:

• Whether the monoid is finite, in which case it is possible to enumerate the elements, and construct a Cayley table and Cayley graph for the monoid (or when performing congruence enumeration, you get the Cayley graph first, and then the FCRS from that).
• Whether the monoid is a group, in which case the inverses of the generators can be determined as well.
• Whether the monoid is commutative, and if so, whether it is cancellative.

To answer the one final question you may have:

Why? Because it's an interesting problem.

Two generators, two relations

⟨a, b | u₁=v₁, u₂=v₂⟩, where |u₁| + |v₁| + |u₂| + |v₂| ≤ 11

1. Swapping the two sides of a defining relation, so u=v becomes v=u.
2. Swapping the two defining relations, so ⟨a, b | u₁=v₁, u₂=v₂⟩ becomes ⟨a, b | u₂=v₂, u₁=v₁⟩.
3. Replacing a with b, and vice versa, within all defining relations.
4. Reversing both sides of each defining relation.

I also skip instances where a defining relation is the tautology u=u, or of the form u=v with both |u| ≤ 1 and |v| ≤ 1. (Note that this discards some "legitimate" instances, namely the two-generator one-relation monoids with sum-of-sides N, which can be presented with two relations and with sum-of-sides N+1: ⟨a, b | u=v, a=a⟩. However, I enumerate one-relation monoids up to length 10 below, which are exactly the missing presentations here.)

The enumeration

• Monoids with two generators and two relations

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

Read the proof:

• A two-relation monoid does not have finite derivation type

• ⟨a, b | bab=aaa, bbbb=1⟩

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

Read the proof:

• The monoid ⟨a, b | aba=aa, baa=aab⟩ has no finite complete presentation

Resolving the status of the 17 remaining length 11 hard instances 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!

Finite monoids

Of the 28,551 instances in the enumeration, 18,867 are presentations of finite monoids. I've classified them up to (anti-)isomorphism, and I believe there are exactly 555 essentially unique finite monoids that appear. Some are quite small:

• ⟨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.
• ⟨a, b | ab=a, ba=b⟩ is the smallest non-commutative monoid in the enumeration, with three elements.

• ⟨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 | bab=aa, bbb=1⟩ 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 b.)

• The length 10 maximum is 1083 elements, achieved by ⟨a, b | aaa=1, abbbba=b⟩. The rewriting system consists of 11 rules and so is not too bad, but here is an explicit description of this monoid:
  • The group with the same presentation has 1080 elements, and is isomorphic to the direct product ℤ₉ ⨯ SL(2, 5).
  • One possible isomorphism maps the generators a and b to the following elements, a := (3, A),    b := (1, B) where: A :=

    0	1
    4	4

    ,    B :=

    0	2
    2	3

    
    
  • In the group, b⁹⁰ = 1, so every element can be expressed as a word involving b, but this doesn't hold in the monoid.
  • Thus, the monoid with this presentation has three more elements than the group: 1, a, and a².
  • It follows that every element of this monoid can be represented as a triple, consisting of an integer, a 2x2 integer matrix, and a boolean flag that is set for pure powers of a.
  • The monoid operation is defined to perform the group operation on the first two components of each triple, and "Boolean and" on the third component.
  • Here is an explicit realization of the monoid operation in the form of a short Swift program, to verify that the two generators satisfy the defining relations and generate a monoid of the correct size.
• The length 11 maximum is ≥ 2,361,964 elements, with top candidates ⟨a, b | aaba=bab, bbbb=1⟩ and ⟨a, b | aaaa=1, ababba=b⟩. In fact, they're isomorphic, but the isomorphism is not yet recorded in the enumeration.
  • I have not been able to get Knuth-Bendix completion to finish with either of these two presentations. Todd-Coxeter congruence enumeration succeeds though, and outputs a rewriting system with more than 100,000 rules for the first of the two, and 61,000 rules for the second. These are by far the largest rewriting systems in my collection; all the rest are under 100 rules each.
  • I have yet to come up with an explicit description of this monoid, if one even exists.
  • Note: I put "≥" above. While the listed monoid has exactly that size, I cannot yet determine if these three hard instances are finite or infinite, so of course it is possible that one of them is a finite monoid with more than 2,361,964 elements:
    • ⟨a, b | aaaa=1, ababb=ba⟩
    • ⟨a, b | aaa=1, ababbb=ba⟩
    • ⟨a, b | aaa=1, babbb=aba⟩
• How big is the largest finite monoid with a presentation of length 12? What about 13?

Two generators, one relation

The enumeration

Explore:

• Monoids with two generators and one relation

• ⟨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 | ababba=1⟩ is 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.

Related work

• Off with the head: termination provers and the word problem for 1-relation monoids
• Certifying the decidability of the word problem in monoids at large

Minor results

(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.)

(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.

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²

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

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

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

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

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

(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}.

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²