| Look up a monoid with two generators, and one or two defining relations: |
|
|
Details:
|
| Jump directly to an enumeration: |
My interest in finitely-presented monoids started with the realization that the Swift compiler can use 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 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 obvious how 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.)
The above 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 tricky. 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⟩
While the general case is undecidable, the word problem can be successfully solved in many cases using Knuth-Bendix completion.
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 by a process which can 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, does Knuth-Bendix completion always succeed?
The answer there is "no". Successful completion can depend on the choice of a reduction order and a generating set for the presented monoid. In many examples, it is not just a matter of waiting long enough, but making the right choices before we begin. One might then ask, if our monoid has a decidable word problem, and we apply Knuth-Bendix completion with carefully chosen initial parameters, and we wait long enough, do we always get an FCRS that can solve our word problem?
The answer is also "no", as shown 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. 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.
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.
I got the idea from Bogdan Grechuk's wonderful book, Polynomial Diophantine Equations: A Systematic Approach. Much like the word problem, no general approach exists that can solve all Diophantine equations, because the general case is undecidable. Grechuk defines an ordering of all such equations, and then proceeds to work through the list, applying various techniques to solve as many instances as possible in order of increasing size. I'm doing a scaled down variation of that, with finitely-presented monoids instead.
Besides solving the word problem, various properties of the presented monoid can be determined from an FCRS:
I've been collecting and analyzing this data for all solved instances. If you click through the links to the monoids below, you'll these properties summarized for each monoid, together with Cayley tables for finite monoids up to size 24, and Cayley graphs for finite monoids up to size 1083.
To actually construct finite complete rewriting systems, I use an adaptation of Knuth-Bendix completion known as morphocompletion, due to John Pedersen. I describe it on the page below:
To answer the one final question you may have:
Why? Because it's an interesting problem.
One-relation monoids have a rich theory, which does not extend to the general case of multiple relations. For an in-depth survey, see The Word Problem for One-Relation Monoids by C.F. Brodda. Here is a brief summary of some of the known results:
The remaining case, where the monoid is cancellative on one side but not the other, has only been solved for a handful of specific families of one-relation monoids.
It is an open question whether the word problem is decidable for all one-relation monoids. It is also an open question if every one-relation monoid can be presented by a finite complete rewriting system. The latter would of course imply the former, but another theoretical possibility is that every one-relation monoid has a decidable word problem, just not via FCRS.
In the world of one-relation monoids, my only result so far is a purely computational one. Basically, what I did is generate an exhaustive list of all monoid presentations with two generators, one relation, and then tried to find a finite complete rewriting system for each one, up to sum-of-sides ≤ 11:
⟨a, b | u=v⟩
where:
|u| + |v| ≤ 11
Explore:
To cut down on the work, I use the fact that a large number of monoid presentations in this list are isomorphic or anti-isomorphic to each other, by some combination of the following:
If one instance in such an equivalence class has a finite complete presentation, they all do, so it suffices to only keep one instance from each such equivalence class.
I also skip presentations where the defining relation is the tautology u=u, or of the form u=v with both |u| ≤ 1 and |v| ≤ 1. All such presentations define the free monoid on one or two generators.
After this filtering has taken place, 5944 instances remain.
I can find a finite complete rewriting system for all instances in the enumeration except for four hard instances. The first one is ⟨a, b | abbaab=ba⟩, with length 8. Unlike the two-relation case, I have not resolved the status of any of the hard instances, except to observe that they are all cancellative, so their word problem can be solved by embedding in the group with the same presentation.
Thus, with finite complete rewriting systems for all of the non-cancellative instances on hand, I can conclude that every one-relation monoid has a known decidable word problem up to sum-of-sides ≤ 11.
Open Question 1: Can the four remaining one-relation monoids in the enumeration be presented by finite complete rewriting systems?
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| ≤ 11. Check out their publications:
Let's take a look at the first few presentations:
The above are all special monoids (with defining relation w=1), but they are not groups. It doesn't take long for the first groups to appear:
Up to length 11, finding a finite complete rewriting system for all special monoids that are not groups is quite simple, because they all admit one over the original alphabet {a, b}. However, among the special monoids that present groups, finding a finite complete rewriting system requires the use of morphocompletion to introduce new auxiliary generators in almost all instances. In fact, the only groups in the one-relation enumeration where completion converges over the original alphabet are the three listed above!
The first group we encounter that requires expanding the generating set has a presentation of length 4:
A number of cancellative one-relation monoids in the enumeration turn out to be submonoids of the Braid group B3 mentioned above:
One of the unsolved hard instances, ⟨a, b | abababa=baab⟩, also happens to be a submonoid of B3.
There are no finite monoids in the one-relation enumeration, because it takes at least two relations to present a finite monoid with two generators.
I've found finite complete rewriting systems for a handful of one relation monoids that have stumped others, which is perhaps mildly interesting.
(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 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⟩. The second one is anti-isomorphic to ⟨a, b | aaabaaab=aba⟩. Both are FCRS.
(3) The next example is from The Word Problem for One-Relation Monoids, mentioned above:
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 monoid presented by ⟨a, b | bababbbabba=a⟩ admits a finite complete rewriting system.
(4) In the paper On the Dehn functions of a class of monadic one-relation monoids by the same author as the one-relation monoid survey, he defines this family of monoids:
ΠN := ⟨a,b | baa(ba)N=a⟩
At one point he asks:
Does ΠN admit a finite complete rewriting system for all N ≥ 2?
While I do not have a proof of the general case, I believe they all admit finite complete rewriting systems. In each case I tried, it is sufficient to add two letters c=ab and d=ba. For example, here are the first few up to N ≤ 7:
The Baumslag-Gersten group is a one-relation group with presentation ⟨a, b | b-1a-1bab-1ab=aa⟩, not a one-relation monoid. (One possible monoid presentation is shown below.)
As mentioned above, every one-relator group has a decidable word problem. The group's Dehn function in a sense measures the complexity of applying Magnus's algorithm, and the Dehn function of the Baumslag-Gersten group is an iterated tower of exponentials. However, the word problem in the Baumslag-Gersten group can actually be solved in polynomial time, as shown in The Word Problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
This quote appears in the paper titled HNN extensions and stackable groups:
Although it is an open question whether Baumslag’s nonmetabelian group, or any other group with nonelementary Dehn function, can have a finite complete rewriting system, [...]
I claim that the Baumslag-Gersten group is FCRS. The below page shows how to obtain one if we start from this monoid presentation:
I do not know the exact time complexity of word reduction in this FCRS. It uses a recursive path order to establish termination, so it is possible that it is something equally bad as the Dehn function.
Here is an input file for kbmag which also reproduces the result:
_RWS := rec (
isRWS := true,
ordering := "wreathprod",
generatorOrder := [e,f,a,c,g,b,d],
level := [1,1,1,1,2,3,4],
equations := [
# group inverses
[a*c, IdWord],
[c*a, IdWord],
[b*d, IdWord],
[d*b, IdWord],
# the original relation
[d*c*b*a*d*a*b, a*a],
# auxiliary generators
[e, d*c*b],
[f, c*e],
[g, d*a*b]
]
);
I've also investigated monoids with two defining relations.
Similar to the one-relation case, it is easy to generate an exhaustive list of all monoid presentations with two generators, two relations, and sum-of-sides ≤ 11:
⟨a, b | u1=v1, u2=v2⟩
where:
|u1| + |v1| + |u2| + |v2| ≤ 11
Explore:
In addition to the symmetries described in the one-relation case, there is one more:
After filtering for symmetry, 28,551 instances remain. I can find a finite complete rewriting system for all but 17 hard instances.
One of the hard instances has length 10, while the rest have length 11. My main result concerning two-relation monoids 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 (this monoid is "not FCRS"). In fact, just like Squier's S1, it does not have finite derivation type.
Read the proof: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, and they're actually isomorphic to each other:
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:Open Question 2: Does ⟨a, b | aba=aa, baa=aab⟩ also fail to have finite derivation type?
Open Question 3: Do any of the 15 remaining unresolved two-relation hard instances admit presentations by finite complete rewriting systems?
A notable change from one relations to two is the appearance of finite monoids.
Of the 28,551 instances in this enumeration, 18,868 are finite. I've classified them up to (anti-)isomorphism, and I believe exactly 556 unique finite monoids appear. Some are quite small:
Some nice and short presentations of various classic finite groups then appear:
Here is a "Busy Beaver"-esque problem: what is the largest finite monoid you can present with two generators, two relations, and length N? (The Busy Beaver problem asks, given a Turing machine with m states and n symbols, what is the longest possible running time among all such machines that halt?)
The length 10 maximum is 1083 elements, achieved by ⟨a, b | aaa=1, abbbba=b⟩. The rewriting system consists of 11 rules, and we can give an even simpler explicit description of this monoid:
| 0 | 1 |
| 4 | 4 |
| 0 | 2 |
| 2 | 3 |
The length 11 maximum (so far, see below) is 2,361,964 elements, achieved by ⟨a, b | aaba=bab, bbbb=1⟩. The rewriting system consists of 112,169 rules.
Another difficult presentation is ⟨a, b | aaa=1, ababbb=ba⟩. This is a finite monoid with only 336 elements.
I still have not been able to resolve the finiteness of one of the hard instances:
⟨a, b | aaa=1, babbb=aba⟩
The group with the same presentation was the subject of another MathOverflow question. At the time of writing, that question is unsolved, and all I know is that the monoid has 3 more elements than the group, because b8 is a central idempotent in the monoid. The possibility remains that the above presents a finite monoid with more than 2,361,964 elements.
Open Question 4: Is the group presented by ⟨a, b | aaa=1, babbb=aba⟩ finite? What is its order?
It is undecidable if a monoid presentation defines a finite monoid, and it appears that even here, the difficulty of establishing finiteness increases rapidly.
Open Question 5: What is the cardinality of the largest finite monoid with a presentation of length 12? What about 13?