|
The functions in this section provide access to basic information stored for a
rewrite monoid M.
The i-th defining generator for M.
A sequence containing the defining generators for M.
Ngens(M) : MonRWS -> RngIntElt
The number of defining generators for M.
Relations(M) : MonRWS -> [MonFPRel]
A sequence containing the defining relations for M. The relations
will be given between elements of the free monoid of which M is a
quotient. In these relations the (image of the) left hand side (in M)
will always be greater than the (image of the) right hand side (in M)
in the ordering on words used to construct M.
Nrels(M) : MonRWS -> RngIntElt
The number of relations in M.
The ordering of M.
The parent monoid M for the word w.
We illustrate the access operations using the following
presentation of S 4.
> FM<a,b> := FreeMonoid(2);
> Q := quo< FM | a^2=1, b^3=1, (a*b)^4=1 >;
> M<x,y> := RWSMonoid(Q);
> print M;
A confluent rewrite monoid.
Generator Ordering = [ a, b ]
Ordering = ShortLex.
The reduction machine has 12 states.
a^2 = Id(FM)
b^3 = Id(FM)
b * a * b * a * b = a * b^2 * a
b^2 * a * b^2 = a * b * a * b * a
b * a * b^2 * a * b * a = a * b * a * b^2 * a * b
> print Order(M);
24
> print M.1;
x
> print M.1*M.2;
x * y
> print Generators(M);
[ x, y ]
> print Ngens(M);
2
> print Relations(M);
[ a^2 = Id(FM), b^3 = Id(FM), b * a * b * a * b = a * b^2 * a, b^2 * a * b^2 = a
* b * a * b * a, b * a * b^2 * a * b * a = a * b * a * b^2 * a * b ]
> print Nrels(M);
5
> print Ordering(M);
ShortLex
Returns true if M is confluent, false otherwise.
Given a confluent monoid M return true if M has finite order
and false otherwise. If M does have finite order also return
the order of M.
# M : MonRWS -> RngIntElt
Given a monoid M defined by a confluent presentation, this function
returns the cardinality of M. If the order of M is known
to be infinite ∞ is returned.
We construct a threefold cover of A 6.
> FM<a,b> := FreeMonoid(2);
> Q := quo< FM | a^3=1, b^3=1, (a*b)^4=1, (a*b^2)^5 = 1 >;
> M := RWSMonoid(Q);
> print Order(M);
1080
> IsConfluent(M);
true
We construct the 2-generator free abelian group and compute
its order. The result Infinity indicates that the group has
infinite order.
> FM<a,A,b,B> := FreeMonoid(4);
> Q := quo< FM | a*A=1, A*a=1, b*B=1, B*b=1, B*a*b=a>;
> M := RWSMonoid(Q);
> Order(M);
Infinity
We construct the Weyl group E 8 and test whether or not
it has finite order.
> FM<a,b,c,d,e,f,g,h> := FreeMonoid(8);
> Q := quo< FM | a^2=1, b^2=1, c^2=1, d^2=1, e^2=1, f^2=1, g^2=1,
> h^2=1, b*a*b=a*b*a, c*a=a*c, d*a=a*d, e*a=a*e, f*a=a*f,
> g*a=a*g, h*a=a*h, c*b*c=b*c*b, d*b=b*d, e*b=b*e, f*b=b*f,
> g*b=b*g, h*b=b*h, d*c*d=c*d*c, e*c*e=c*e*c, f*c=c*f,
> g*c=c*g, h*c=c*h, e*d=d*e, f*d=d*f, g*d=d*g, h*d=d*h,
> f*e*f=e*f*e, g*e=e*g, h*e=e*h, g*f*g=f*g*f, h*f=f*h,
> h*g*h=g*h*g>;
> M := RWSMonoid(Q);
> print IsFinite(M);
true
> isf, ord := IsFinite(M);
> print isf, ord;
true 696729600
Id(M) : MonRWS -> MonRWSElt
M ! 1 : MonRWS, RngIntElt -> MonRWSElt
Construct the identity word in M.
Given a rewrite monoid M defined on r generators and a sequence
[i1, ..., is] of integers lying in the range [1, r],
construct the word M.i1 * M.i2 * ... * M.is.
We construct the Fibonacci group F(2, 7), and it's identity.
> FM<a,A,b,B,c,C,d,D,e,E,f,F,g,G> := FreeMonoid(14);
> Q := quo< FM | a*A=1, A*a=1, b*B=1, B*b=1, c*C=1, C*c=1,
> d*D=1, D*d=1, e*E=1, E*e=1, f*F=1, F*f=1, g*G=1, G*g=1,
> a*b=c, b*c=d, c*d=e, d*e=f, e*f=g, f*g=a, g*a=b>;
> M := RWSMonoid(Q : TidyInt := 1000);
> print Id(M);
Id(M)
> print M!1;
Id(M)
> Order(M);
29
Having constructed a rewrite monoid M one can perform arithmetic with words
in M. Assuming we have u, v ∈M then the product u * v will be computed
as follows:
- (i)
- The product w = u * v is formed as a product in the appropriate
free monoid.
- (ii)
- The word w is reduced using the reduction machine associated
with M.
If M is confluent, then w will be the unique minimal word that represents
u * v under the ordering of M. If M is not confluent, then there are
some pairs of words which are equal in M, but which reduce to distinct words,
and hence w will not be a unique normal form. Note that:
- (i)
- Reduction of w can cause an increase in the length of w. At
present there is an internal limit on the length of a word -- if this limit
is exceeded during reduction an error will be raised. Hence any word operation
involving reduction can fail.
- (ii)
- The implementation is designed more with speed of execution in
mind than with minimizing space requirements; thus, the reduction machine is
always used to carry out word reduction, which can be space-consuming,
particularly when the number of generators is large.
Product of the words w and v.
The n-th power of the word w, where n is a positive or zero integer.
Given words w and v belonging to the same monoid, return true
if w and v reduce to the same normal form, false otherwise. If M is
confluent this tests for equality. If M 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 monoid, return false
if w and v reduce to the same normal form, true otherwise. If M is
confluent this tests for non-equality. If M is non-confluent
then two words which are the same may reduce to different normal forms.
IsIdentity(w) : MonRWSElt -> BoolElt
Returns true if the word w is the identity word.
The length of the word w.
Eltseq(u) : MonRWSElt -> [ RngIntElt ]
The sequence Q obtained by decomposing the element u of a rewrite monoid
into its constituent generators. Suppose u is a word in the rewrite
monoid M. If u = M.i1 ... M.im, then Q[j] = ij, for
j = 1, ..., m.
We illustrate the word operations by applying them to elements of the Fibonacci
monoid FM(2, 5).
> FM<a,b,c,d,e> := FreeMonoid(5);
> Q:=quo< FM | a*b=c, b*c=d, c*d=e, d*e=a, e*a=b >;
> M<a,b,c,d,e> := RWSMonoid(Q);
> a*b*c*d;
b^2
> (c*d)^4 eq a;
true
> IsIdentity(a^0);
true
> IsIdentity(b^2*e);
false
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|