⟨🍎🍌🐈🐶🐘 | Slava's Monoid Zoo | 🐘🐶🐈🍌🍎⟩

Return to my home page.

Contents

Introduction

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:

• 🍌🍎🍌 = 🍎🍎🍎
• 🍌🍌🍌 = 🍌🍌

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 a8 and a10, 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 S1, with five generators and five relations:

S1 := ⟨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, S1 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.

Two generators, two relations

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 as "hard instances" 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 S1, 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