Internally a monoid presentation P of the group Q is constructed. By default the generators of P are taken to be g_1, (g_1)^(-1), ..., g_n, (g_n)^(-1) where g_1, ..., g_n are the generators of Q. The relations of P are taken to be the relations of Q. The trivial relations between the generators and their inverses are also added. The Knuth--Bendix completion procedure for monoids is now run on P. Regardless of whether or not the completion procedure succeeds the result will be a rewrite group, G, containing a reduction machine and a sequence of reduction relations. If the procedure succeeds G will be marked as confluent, and the word problem for G is therefore decidable. If, as is very likely, the procedure fails then G will be marked as non-confluent. In this case G will contain both the reduction relations and the reduction machine computed up to the point of failure.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 group. The best values to set for these limits varies from example to example.
TidyInt = n: RngIntElt Default: 100After finding n 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.)
MaxRelations = n: RngIntElt Default: 32767Limit the maximum number of reduction equations to n.
MaxStates = n: RngIntElt Default:Limit the maximum number of states of the finite state automaton used for word reduction to n. 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 = n: RngIntElt Default: 32767Limit the maximum allowed length that a word can reach during reduction to n. It is only likely to be exceeded when using recursive ordering on words. This limit is usually not needed.
MaxStoredLen = <l,r>: Tup Default:Only equations in which the left and right hand sides have lengths at most l and r, respectively, 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 group defined by the equations changes.
MaxOverlapLen = n: RngIntElt Default:Only overlaps of total length at most n are processed. Of course this may cause the overlap search to complete on a set of equations that is not confluent.
Sort: BoolElt Default: false
MaxOpLen = n: 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. n should be a non-negative integer. If n is positive, then only equations with left hand sides having length at most n are output. If n is zero, then all equations are sorted by length. Of course, if n is positive, there is a danger that the group defined by the output equations may be different from the original.
RabinKarp = <l, n>: 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. 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. n should be set higher than the expected final number of equations.
GeneratorOrder: SeqEnum Default:Give an ordering for the generators of P. This ordering affects the ordering of words in the alphabet. If not specified the ordering defaults to [g_1, (g_1)^(-1), ..., g_n, (g_n)^(-1)] where g_1, ..., g_n are the generators of Q.
ConfNum = n: RngIntElt Default: 500If n 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 n = 0, then the fast confluence check is performed only when the search for overlaps is complete.
Ordering: MonStgElt Default: "ShortLex"
Levels: SeqEnum Default:
Weights: SeqEnum Default:Ordering := "ShortLex": Use the short-lex ordering on words. 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 words. There are various ways to define this. Perhaps the quickest is as follows. Let u and v be words 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.
- a = b and u' > v';
- a > b and u > v';
- b > a and u' > v.
Ordering := "WTShortLex": 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 words involving generators of the same level are ordered using short-lex, but all words 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.
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.
> F<a,b> := FreeGroup(2);
> Q := quo< F | a*a=1, b*b=b^-1, a*b^-1*a*b^-1*a=b*a*b*a*b>;
> G := RWSGroup(Q);
> 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
> FG<a,b> := FreeGroup(2);
> Q := quo< FG | b^-1*a^2*b=a^3>;
> G := RWSGroup(Q : MaxRelations := 100, MaxStates := 200,
> 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
> FG<a,b,c> := FreeGroup(3);
> Q := quo< FG | b*a=a*b*c, c*a=a*c, c*b=b*c>;
> G := RWSGroup(Q : 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
Construct the identity word in G.
Given a rewrite group G defined on r generators and a sequence [i_1, ..., i_s] of integers lying in the range [ - r, r], excluding 0, construct the word G.|i_1|^(epsilon_1) * G.|i_2|^(epsilon_2) * ... * G.|i_s|^(epsilon_s) where epsilon_j is +1 if i_j is positive, and -1 if i_j is negative.
> FG<a,b,c,d,e,f,g> := FreeGroup(7); > Q := quo< FG | a*b=c, b*c=d, c*d=e, d*e=f, e*f=g, f*g=a, g*a=b>; > G := RWSGroup(Q : TidyInt := 1000); > print Id(G); Id(G) > print G!1; Id(G)
Having constructed a rewrite group G one can perform arithmetic with words in G. Assuming we have u, v in G then the product u * v will be computed as follows:
Product of the words w and v.
Product of the word u by the inverse of the word v, i.e. the word u * v^(-1).
The n-th power of the word w.
Conjugate of the word u by the word v, i.e. the word v^(-1) * u * v.
The inverse of the word w.
Commutator of the words u and v, i.e., the word u^(-1)v^(-1)uv. Here u and v must belong to the same group.
Given r words u_1, ..., u_r belonging to a common group, return their commutator. Commutators are left-normed, so they are evaluated from left to right.
Given words w and v belonging to the same group, return true if w and v reduce to the same normal form, false otherwise. If G is confluent this tests for equality. If G is non-confluent then two words which are the same may not reduce to the same normal form.
Given words w and v belonging to the same group, return false if w and v reduce to the same normal form, true otherwise. If G is confluent this tests for non-equality. If G is non-confluent then two words which are the same may reduce to different normal forms.
True if the word w is the identity word.
The length of the word w.
The sequence Q obtained by decomposing the element u of a rewrite group into its constituent generators and generator inverses. Suppose u is a word in the rewrite group G. Then, if u = G.i_1^(e_1) ... G.i_m^(e_m), with each e_i equaling plus or minus 1, then Q[j] = i_j if e_j = + 1 and Q[j] = - i_j if e_j = (-1), for j = 1, ..., m.
> FG<a,b,c,d,e> := FreeGroup(5); > Q := quo< FG | a*b=c, b*c=d, c*d=e, d*e=a, e*a=b>; > G<a,b,c,d,e> := RWSGroup(Q); > print a*b^-1; e^-1 > print a/b; e^-1 > print (c*d)^4; a > print a^b, b^-1*a*b; a a > print a^-2, Inverse(a)^2; d d > print c^-1*d^-1*c*d eq (c,d); true > print IsIdentity(a*b*c^-1); true > print #(c*d); 1