Suppose F is a finitely presented group. Internally, the first step is to construct a presentation for a monoid M. By default, the generators of M are taken to be g1, g1 - 1, ..., gn, gn - 1, where g1, ..., gn are the generators of F. The relations for M are taken to be the relations of F together with the trivial relations g1g1 - 1 = g1 - 1g1 = 1. The Knuth--Bendix completion procedure for monoids is now applied to M. Regardless of whether or not the completion procedure succeeds, the result will be a rewrite monoid, M, containing a reduction machine and a sequence of reduction relations. If the procedure succeeds M will be marked as confluent, and the word problem for M is therefore decidable. If, as is very likely, the procedure fails then M will be marked as non-confluent. In this case M will contain both the reduction relations and the reduction machine computed up to the point of failure. Reductions made using these relations will be correct in F, but words that are equal in F are not guaranteed to reduce to the same word.The Knuth--Bendix procedure requires ordering to be defined on both the generators and the words. The default generator ordering is that induced by the ordering of the generators of F while the default ordering on strings is the ShortLex order. We give a simple example and then discuss the parameters that allow the user to specify these two orderings.
As the Knuth--Bendix procedure will more often than not run forever, some conditions must be specified under which it will stop. These take the form of limits that are placed on certain variables, such as the number of reduction relations. If any of these limits are exceeded during a run of the completion procedure it will fail, returning a non-confluent rewrite monoid. The optimal values for these limits vary from example to example. The various parameters that allow the user to specify the limits for these variables will be described in a subsequent section.
We construct the Von Dyck (2, 3, 5) group. Since a string ordering is not specified the default ShortLex ordering is used. Similarly, since a generator ordering is not specified, the default generator ordering, in this case [ a, a - 1, b, b - 1 ], is used.
> FG<a,b> := FreeGroup(2);
> F := quo< FG | a*a=1, b*b=b^-1, a*b^-1*a*b^-1*a=b*a*b*a*b>;
> G := RWSGroup(F);
> G;
A confluent rewrite group.
Generator Ordering = [ a, a^-1, b, b^-1 ]
Ordering = ShortLex.
The reduction machine has 39 states.
The rewrite relations are:
a^2 = Id(F)
b * b^-1 = Id(F)
b^-1 * b = Id(F)
b^2 = b^-1
b * a * b * a * b = a * b^-1 * a * b^-1 * a
b^-2 = b
b^-1 * a * b^-1 * a * b^-1 = a * b * a * b * a
a^-1 = a
a * b^-1 * a * b^-1 * a * b = b * a * b * a * b^-1
b * a * b^-1 * a * b^-1 * a = b^-1 * a * b * a * b
a * b * a * b * a * b^-1 = b^-1 * a * b^-1 * a * b
b^-1 * a * b * a * b * a = b * a * b^-1 * a * b^-1
b * a * b * a * b^-1 * a * b * a = a * b^-1 * a * b * a * b^-1 * a * b^-1
b^-1 * a * b^-1 * a * b * a * b^-1 * a = a * b * a * b^-1 * a * b * a * b
b^-1 * a * b * a * b^-1 * a * b * a * b^-1 = b * a * b^-1 * a * b * a * b^-1
* a * b
b * a * b^-1 * a * b * a * b^-1 * a * b^-1 = (b^-1 * a * b * a)^2
b^-1 * a * b * a * b^-1 * a * b * a * b = (b * a * b^-1 * a)^2
b * a * b^-1 * a * b * a * b^-1 * a * b * a = a * b * a * b^-1 * a * b * a *
b^-1 * a * b
Attempt to construct a confluent presentation for the finitely presented group F using the Knuth-Bendix completion algorithm. In this section we describe how the user can specify the generator order and the ordering on strings.GeneratorOrder: SeqEnum Default:Give an ordering for the generators. This ordering affects the ordering of words in the alphabet. If not specified the ordering defaults to the order induced by F's generators, that is [g1, ..., gn] where g1, ..., gn are the generators of F.Ordering: MonStgElt Default: "ShortLex"Levels: SeqEnum Default:Weights: SeqEnum Default:Ordering := "ShortLex": Use the short-lex ordering on strings. Shorter words come before longer, and for words of equal length lexicographical ordering is used, using the given ordering of the generators.Ordering := "Recursive" | "RtRecursive": Use a recursive ordering on strings. There are various ways to define this. Perhaps the quickest is as follows. Let u and v be strings in the generators. If one of u and v, say v, is empty, then u ≥v. Otherwise, let u=u' a and v=v' b, where a and b are generators. Then u > v if and only if one of the following holds:
The RtRecursive ordering is similar to the Recursive ordering, but with u=au' and v=bv'. Occasionally one or the other runs significantly quicker, but usually they perform similarly.
- (i)
- a = b and u' > v';
- (ii)
- a > b and u > v';
- (iii)
- b > a and u' > v.
Ordering := "WtLex": Use a weighted-lex ordering. Weights should be a sequence of non-negative integers, with the i-th element of Weights giving the weight of the i-the generator. The length of Weights must equal the number of generators. The length of words in the generators is then computed by adding up the weights of the generators in the words. Otherwise, ordering is as for short-lex.
Ordering := "Wreath": Use a wreath-product ordering. Levels should be a sequence of non-negative integers, with the i-th element of Levels giving the level of the i-the generator. The length of Levels must equal the number of generators. In this ordering, two strings involving generators of the same level are ordered using short-lex, but all strings in generators of a higher level are larger than those involving generators of a lower level. That is not a complete definition; one can be found in [Sim94, pp. 46--50]. Note that the recursive ordering is the special case in which the level of generator number i is i.
> F<a, b> := Group< a, b | b^-1*a^2*b=a^3>;
> G := RWSGroup(F : Ordering :="Recursive");
> G;
A confluent rewrite group.
Generator Ordering = [ a, a^-1, b, b^-1 ]
Ordering = Recursive.
The reduction machine has 7 states.
The rewrite relations are:
a * a^-1 = Id(FG)
a^-1 * a = Id(FG)
b * b^-1 = Id(FG)
b^-1 * b = Id(FG)
a^3 * b^-1 = b^-1 * a^2
a^2 * b = b * a^3
a^-1 * b^-1 = a^2 * b^-1 * a^-2
a^-1 * b = a * b * a^-3
A confluent presentation of a free nilpotent group of rank 2 and class 2 is constructed by the following code. Note that the lower weight generators (in the sense of nilpotency class) need to come first in the ordering of generators.
> FG<a,b,c> := FreeGroup(3);
> F := quo< FG | b*a=a*b*c, c*a=a*c, c*b=b*c>;
> G := RWSGroup(F : Ordering :="Recursive",
> GeneratorOrder := [c,c^-1,b,b^-1,a,a^-1]);
> G;
A confluent rewrite group.
Generator Ordering = [ c, c^-1, b, b^-1, a, a^-1 ]
Ordering = Recursive.
The reduction machine has 7 states.
The rewrite relations are:
c * c^-1 = Id(FG)
c^-1 * c = Id(FG)
b * b^-1 = Id(FG)
b^-1 * b = Id(FG)
a * a^-1 = Id(FG)
a^-1 * a = Id(FG)
b * a = a * b * c
c * a = a * c
c * b = b * c
c^-1 * a = a * c^-1
c * a^-1 = a^-1 * c
c^-1 * b = b * c^-1
c * b^-1 = b^-1 * c
b^-1 * a = a * b^-1 * c^-1
b^-1 * a^-1 = a^-1 * b^-1 * c
c^-1 * a^-1 = a^-1 * c^-1
c^-1 * b^-1 = b^-1 * c^-1
b * a^-1 = a^-1 * b * c^-1
In this section we introduce the various parameters used to control the execution of the Knuth-Bendix procedure.
Attempt to construct a confluent presentation for the finitely presented group F using the Knuth-Bendix completion algorithm. We present details of the various parameters used to control the execution of the Knuth-Bendix.MaxRelations: RngIntElt Default: 32767Limit the maximum number of reduction equations to MaxRelations.TidyInt: RngIntElt Default: 100After finding TidyInt new reduction equations, the completion procedure interrupts the main process of looking for overlaps, to tidy up the existing set of equations. This will eliminate any redundant equations performing some reductions on their left and right hand sides to make the set as compact as possible. (The point is that equations discovered later often make older equations redundant or too long.)RabinKarp: Tup Default:Use the Rabin-Karp algorithm for word-reduction on words having length at least l, provided that there are at least n equations, where RabinKarp := <l, n>. This uses less space than the default reduction automaton, but it is distinctly slower, so it should only be used when seriously short of memory. Indeed this option is only really useful for examples in which collapse occurs - i.e. at some intermediate stage of the calculation there is a very large set of equations, which later reduces to a much smaller confluent set. Collapse is not uncommon when analysing pathological presentations of finite groups, and this is one situation where the performance of the Knuth--Bendix algorithm can be superior to that of Todd-Coxeter coset enumeration. The best setting for RabinKarp varies from example to example - generally speaking, the smaller l is, the slower things will be, so set it as high as possible subject to not running out of memory. The number of equations n should be set to a value greater than the expected final number of equations.MaxStates: RngIntElt Default:Limit the maximum number of states of the finite state automaton used for word reduction to MaxStates. By default there is no limit, and the space allocated is increased dynamically as required. The space needed for the reduction automaton can also be restricted by using the RabinKarp parameter. This limit is not usually needed.MaxReduceLen: RngIntElt Default: 32767Limit the maximum allowed length that a word can reach during reduction to MaxReduceLen. It is only likely to be exceeded when using the recursive ordering on words. This limit is usually not needed.ConfNum: RngIntElt Default: 500If ConfNum overlaps are processed and no new equations are discovered, then the overlap searching process is interrupted, and a fast check for confluence performed on the existing set of equations. Doing this too often wastes time, but doing it at the right moment can also save a lot of time. If ConfNum = 0, then the fast confluence check is performed only when the search for overlaps is complete.Warning: Changing the default setting on any of the following parameters may either cause the procedure to terminate without having found a confluent presentation or may change the underlying group.
MaxStoredLen: Tup Default:Only equations in which the left and right hand sides have lengths at most l and r, respectively, where MaxStoredLen := <l, r> are kept. Of course this may cause the overlap search to complete on a set of equations that is not confluent. In some examples, particularly those involving collapse (i.e. a large intermediate set of equations, which later simplifies to a small set), it can result in a confluent set being found much more quickly. It is most often useful when using a recursive ordering on words. Another danger with this option is that sometimes discarding equations can result in information being lost, and the monoid defined by the equations changes.MaxOverlapLen: RngIntElt Default:Only overlaps of total length at most MaxOverlapLen are processed. Of course this may cause the overlap search to complete on a set of equations that is not confluent.Sort: BoolElt Default: falseMaxOpLen: RngIntElt Default: 0If Sort is set to {true} then the equations will be sorted in order of increasing length of their left hand sides, rather than the default, which is to leave them in the order in which they were found. MaxOpLen should be a non-negative integer. If MaxOpLen is positive, then only equations with left hand sides having length at most MaxOpLen are output. If MaxOpLen is zero, then all equations are sorted by length. Of course, if MaxOpLen is positive, there is a danger that the monoid defined by the output equations may be different from the original.
Set the verbose printing level for the Knuth-Bendix completion algorithm. Setting this level allows a user to control how much extra information on the progress of the algorithm is printed. Currently the legal values for v are 0 to 3 inclusive. Setting v to 0 corresponds to the `-silent' option of KBMAG in which no extra output is printed. Setting v to 2 corresponds to the `-v' (verbose) option of KBMAG in which a small amount of extra output is printed. Setting v to 3 corresponds to the `-vv' (very verbose) option of KBMAG in which a huge amount of diagnostic information is printed.
The functions in this group provide access to basic information stored for a rewrite group G.
The i-th defining generator for G. The integer i must lie in the range [ - r, r], where r is the number of group G.
A sequence containing the defining generators for G.
The number of defining generators for G.
A sequence containing the defining relations for G. The relations will be given between elements of the free group of which G is a quotient. In these relations the (image of the) left hand side (in G) will always be greater than the (image of the) right hand side (in G) in the ordering on words used to construct G.
The number of relations in G.
The ordering of G.
> FG<a,b,t> := FreeGroup(3);
> F := quo< FG | t^2=1, b*a=a*b, t*a*t=b>;
> G<x,y,z> := RWSGroup(F);
> G;
A confluent rewrite group.
Generator Ordering = [ a, a^-1, b, b^-1, t, t^-1 ]
Ordering = ShortLex.
The reduction machine has 6 states.
The rewrite relations are:
a * a^-1 = Id(F)
a^-1 * a = Id(F)
b * b^-1 = Id(F)
b^-1 * b = Id(F)
t^2 = Id(F)
b * a = a * b
t * a = b * t
b^-1 * a = a * b^-1
t * b = a * t
b * a^-1 = a^-1 * b
t * a^-1 = b^-1 * t
t^-1 = t
b^-1 * a^-1 = a^-1 * b^-1
t * b^-1 = a^-1 * t
> G.1;
x
> G.1*G.2;
x * y
> Generators(G);
[ x, y, z ]
> Ngens(G);
3
> Relations(G);
[ a * a^-1 = Id(F), a^-1 * a = Id(F), b * b^-1 = Id(F), b^-1 * b = Id(F), t^2 =
Id(F), b * a = a * b, t * a = b * t, b^-1 * a = a * b^-1, t * b = a * t, b *
a^-1 = a^-1 * b, t * a^-1 = b^-1 * t, t^-1 = t, b^-1 * a^-1 = a^-1 * b^-1, t *
b^-1 = a^-1 * t ]
> Nrels(G);
14
> Ordering(G);
ShortLex