A well-known fact is that the Knuth-Bendix completion algorithm does not always terminate, and successful completion can depend both on the choice of reduction order, and the generating set chosen to present the monoid. Thus, finding a finite complete rewriting system may require many attempts. It is undecidable if a given finitely-presented monoid has an FCRS, so the best we can do is heuristics.
To deal with the issue of reduction orders, you can imagine an implementation of Knuth-Bendix completion which runs the completion process with multiple reduction orders in parallel, either as a set of independent tasks, or as a single task that tracks rule orientations across all reduction orders simultaneously. I use the former approach, because it generalizes more easily.
A more difficult question is how to guess any additional "auxiliary generators". I use a technique known as morphocompletion, introduced by John Pedersen in Morphocompletion for one-relation monoids. The idea is not specific to one-relation monoids, and I've also had success applying it to infinite monoids in the two-relation enumeration as well. I will describe my variation of morphocompletion now, which I used to generate my one-relation and two-relation monoid enumerations.
An early example from the one-relation enumeration where no reduction order over the original alphabet completes is ⟨a, b | aba=ab⟩. Completion generates an infinite sequence of rules of the form abna=abn:
Each rule's left-hand side overlaps with the left-hand side of every other rule, so this process cannot end. However, suppose we first introduce a new letter c to the original presentation, together with the defining relation c=ab. Because the new letter is paired with a defining relation of this form, it doesn't give us anything new; it's just a "shortcut".
The point though, is that Knuth-Bendix completion over this extended presentation actually succeeds, for example if we use the shortlex order where a < c < b. This outputs a short rewriting system shown at ⟨a, b | aba=ab⟩, where words over the original alphabet now have normal forms over the extended alphabet. The letter c is called an auxiliary generator.
Let's define an "attempt" as a tuple of parameters that are ultimately handed off to an invocation of the Knuth-Bendix algorithm:
Imagine that there is a queue of such attempts. Some attempts are enqueued at the start of the algorithm, and more might be added later, as described below. The queue of attempts can be drained by one or more parallel worker tasks, where each task runs Knuth-Bendix with those parameters.
A key fact is that most attempts are going to run forever if you let them, so you want to limit the time spent on each attempt, so that the next attempt can begin as quickly as possible. This can be achieved in various ways by counting internal operations in Knuth-Bendix and imposing limits on those counters. Of course, any such limits must be set high enough to allow every instance to solve. Getting the right limits is again, an undecidable problem, more art than science.
The overall morphocompletion algorithm begins by enqueuing an attempt for each reduction order over the original alphabet, without adding any auxiliary generators at first. These attempts are called basic attempts below.
Now, the two most common kinds of reduction orders are the following:
Furthermore, each reduction order above also has a variant where instead of walking the strings being compared from left to right, you can walk them from right to left.
If the presentation has two letters a and b, I take the basic set of orders to be the following:
You can imagine we're starting to explore our search space. It is a giant infinite tree, with the original presentation as the root, and the immediate children being the basic attempts, one for each reduction order.
If at least one basic attempt succeeds, the search stops. If all basic attempts fail, the next step is to explore the search space deeper.
Other orders. The shortlex order generalizes to the Knuth-Bendix order, where arbitrary weights are assigned to letters, and the recursive path order has various generalizations as well, for example we can do right-to-left recursive path with left-to-right (opposite) shortlex over letters of equal degree. Other than producing shorter rewriting systems in a couple of instances, these specific generalizations don't seem to solve anything new in my enumeration.
A minor optimization. If the presentation is anti-isomorphic to itself under some permutation of the letters (that is, isomorphic to its own reversal, for example a one-relation monoid with relation abba=bab), you can skip all of the right-to-left orders, because each such order will arise as a left-to-right order with a different permutation or degree assignment.
If all basic attempts fail, the next thing to attempt is to guess the auxiliary generators directly from the presentation of a one-relation monoid. I call this the "magic" strategy, which is just a name I made up. It does not apply to two-relation monoids, for which we skip directly to the "morph" strategy below.
In the above example ⟨a, b | aba=ab⟩, the right-hand side of the initial rule is ab, and introducing the generator c=ab works. Given a presentation of a one-relation monoid ⟨a, b | u=v⟩ where v has length at least 2, the "magic" strategy adds c=v and then attempts every reduction order over the alphabet {a, b, c}. Pedersen's paper refers to this as the (S1) step. This solves a large number of one-relation monoids, listed under the "Solved by magic" heading on the below page:
For the so-called special one-relation monoids, that is, ones with presentation of the form ⟨a, b | u=1⟩, Pedersen's (S1) strategy doesn't apply, but a similar strategy sometimes works instead. You consider each letter s of the original alphabet:
The above produces up to two sets of candidate generators, one for each letter, where each set consists of two words. Each set can then be attempted with all reduction orders over the extended alphabet (so if the original alphabet has two letters, the extended alphabet has four).
For example, in ⟨a, b | aaaabaaba=1⟩, there are no runs of two or more consecutive b's, so only a is considered and we get one pair of candidate generators, c=aaaaa and d=baab. After adding these two generators to the presentation, completion then succeeds with a recursive path order.
This strategy solves a large number of special one-relation monoids that all happen to present non-Abeliean groups. The two new auxiliary generators become inverses of each other:
Note that this strategy does not solve all non-Abelian groups that appear in the one-relation monoid enumeration; some are solved with the "morph" strategy described next.
Another curious fact. Not every special monoid is a group, but up to length 11, all special monoids that are not groups can be solved without the introduction of auxiliary generators. However, this no longer holds at length 12!
Open Problem. Can the "magic" strategy for one-relation groups be generalized in useful ways?
If all basic attempts fail, and all magic attempts either don't apply or also fail, the next step is to analyze the actual incomplete rewriting systems produced by previous attempts to find more candidate auxiliary generators. This is the most general strategy.
To make this strategy work, there is one detail to add to the description of basic attempts above. At a certain point on each Knuth-Bendix attempt before the overall computation limit is hit, if the rewriting system is not confluent yet, we pause to collect all subwords of all sides of all rewriting rules recorded so far. This factor set is the set of candidate auxiliary generators that we will try to add, if this attempt subsequently fails. Thus, when an attempt succeeds, we get a finite complete rewriting system, but when it fails, we get this list of interesting words.
In the middle of completion, the full factor set of all rewriting rules might be extremely large. My approach to prune the set down is to sort the elements by length, and then by (decreasing) frequency of occurrence, so that the most common factors of each length appear first. (With a few additional tweaks for two-relation monoids, described further down.) I then cut off this space with a "bounding box" consisting of the length and frequency. Every factor of every rule so far eventually appears in a large-enough bounding box, but of course the search space at that point might be too large.
If a completion attempt eventually succeeds, the collected factors from the incomplete state are discarded. But if the attempt fails, those factors are used to form the "next generation" of attempts, which are added to the queue. Each new attempt consists of the following:
Thus, at each failed attempt, our search space branches twice: first, we consider each word in the collected factor set, which adds a new auxiliary generator, which we attempt with various reduction orders.
For example, if all basic attempts failed and the basic attempt with the shortlex order a < b yields a candidate auxiliary generator, we consider each order over {a, b, c} where a < b:
A simple optimization cuts down on the work somewhat here. With a recursive path order, it may happen that we're adding c=u, and u is smaller than c in the extended reduction order. (This cannot happen with a shortlex order, because u has length at least 2.) In this case, the attempt can be skipped, since the resulting rewriting system will contain a rule reducing c to u, with no further occurrences of c among the left-hand sides.
Introducing a single auxiliary generator solves a large number of instances in my enumerations that cannot be solved with one of the reduction orders alone.
The "morph" strategy also generalizes easily to introducing two or more auxiliary generators, as follows. If we allow "depth 1" morph attempts to also collect factors just as basic attempts do, then after all such attempts to add one auxiliary generator fail, we look at the queue again, which has now been refilled by all of those failed depth 1 attempts. Each attempt in the queue will now add 2 auxiliary generators, with various reduction orders. The depth 2 attempts can then generate factors for depth 3, and so on.
For two-generator, one-relation monoids, collecting factors after checking 20 rules for overlaps seems to work well.
Here is a sequence of monoid presentations of increasing length, with an increasing number of auxiliary generators required to find a solution in each:
Here is another interesting "family":
To represent a path in this search space, I use a informal notation consisting of the length and frequency of each attempted factor at each depth. To demonstrate how this all works, the page for each monoid has a link labeled Morphocompletion which points at a separate page. This shows the strategy that was used to solve this monoid, and gives a "demonstration" of how the auxiliary generators were found. Each intermediate "step" consists of the incomplete rewriting system, together with the collected factors.
For example, ⟨a, b | aaabba=baaa⟩ from the list above is a fairly challenging morphocompletion problem, with four auxiliary generators found by the morph:3/2,2/2,3/2,3/0 strategy, explained at Morphocompletion for ⟨a, b | aaabba=baaa⟩.
The maximum morph path explored at a given depth defines a "hypercube" in the auxiliary generator search space. For one relation monoids up to length 11, my "attack plan" consists of this series of hypercubes:
8/7 7/4,6/7 7/3,6/5,6/5 4/3,5/3,4/3,7/2 3/2,5/2,3/2,3/2,3/2 3/2,3/2,3/2,3/2,3/2,3/1
Because the number of reduction orders also blows up at each depth, the total number of attempts grows extremely rapidly. For six auxiliary generators, I only attempt shortlex orders. It is of course possible that the 4 hard instances currently unsolved lie just outside this search space.
For two-relation monoids up to length 11, I collect factors after 80 rules have been processed, instead of 20. This seems to work better in a few examples, but it is a very unscientific observation. The per-attempt limits for completion must be set significantly higher for two relations as well.
Open Problem. When is the best time to collect candidate factors, early in the completion process or late?
On the other hand, it is sufficient to explore a much smaller search space to solve almost all infinite monoids in the two-relation enumeration:
14/2 7/2,14/1 5/1,7/1,8/1
Here are some interesting morphocompletion solutions from the two-relation enumeration:
The two-relation enumeration has a handful of instances where the frequency ranking heuristic is not effective. In those cases, the incomplete rewriting system has a rule of the form xy=yx, where y is a power of a letter a or b, and x is some word. Introducing an auxiliary generator c=x allows completion to succeed, but x does not appear with very high frequency anywhere else in the rewriting system. I use a special heuristic to rank x higher in such cases.
The utility of a heuristic similar to the above was also noted in a paper titled A Homotopical Completion Procedure with Applications to Coherence of Monoids.
Open Problem. Is there a better overall strategy for ranking factors than the ones described above?
The last strategy is not a real strategy at all. In a couple of instances, I found the auxiliary generators either with a very long search, or some other means, so I hardcode the generators when re-creating the enumeration to save time. These are marked as being solved with the "custom" strategy on the web site. Right now there are two:
Finally, there are two exceptional instances in the two-relation enumeration:
They define finite monoids, but one doesn't know that until Knuth-Bendix completion suceeds. Pending a huge breakthrough, these two completely break the "morphocompletion paradigm" of running many short attempts, and must be handled specially. In the first case, the rewriting system is very large, and in the second, many critical pairs must be considered. I solved the first by Todd-Coxeter congruence enumeration, and the second by a single Knuth-Bendix attempt with hardcoded parameters. Both take several minutes to run, which is far longer than the milliseconds needed for all remaining instances in the enumeration.