|
|
|
RWSGroup(F: parameters) : MonFP -> MonRWS
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:
- (i)
- a = b and u' > v';
- (ii)
- a > b and u > v';
- (iii)
- b > a and u' > v.
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.
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.
A confluent presentation is constructed for an infinite non-hopfian group
using the Recursive ordering.
> 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: 32767
Limit the maximum number of reduction equations to MaxRelations.
TidyInt: RngIntElt Default: 100
After 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: 32767
Limit 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: 500
If 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: false
MaxOpLen: RngIntElt Default: 0
If 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.
Ngens(G) : GrpRWS -> RngIntElt
The number of defining generators for G.
Relations(G) : GrpRWS -> [GrpFPRel]
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.
Nrels(G) : GrpRWS -> RngIntElt
The number of relations in G.
The ordering of G.
We illustrate the access operations using the following
presentation of Z wreath C 2.
> 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
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|
|