• « Previous
• Up
• Contents
• Index
• Search
• Next »

Basic Operations

Accessing Monoid Information

The functions in this section provide access to basic information stored for a rewrite monoid M.

M . i : MonRWS, RngIntElt -> MonRWSElt

The i-th defining generator for M.

Generators(M) : MonRWS -> [ MonRWSElt]

A sequence containing the defining generators for M.

NumberOfGenerators(M) : MonRWS -> RngIntElt

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.

NumberOfRelations(M) : MonRWS -> RngIntElt

Nrels(M) : MonRWS -> RngIntElt

The number of relations in M.

Ordering(M) : MonRWS -> String

The ordering of M.

Parent(w) : MonRWSElt -> MonRWS

The parent monoid M for the word w.

> 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

Properties of a Rewrite Monoid

IsConfluent(M) : MonRWS -> BoolElt

Returns true if M is confluent, false otherwise.

IsFinite(M) : MonRWS -> BoolElt, RngIntElt

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.

Order(M) : MonRWS -> RngIntElt

# 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.

> 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

> 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

> 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

Construction of a Word

Identity(M) : MonRWS -> MonRWSElt

Id(M) : MonRWS -> MonRWSElt

M ! 1 : MonRWS, RngIntElt -> MonRWSElt

Construct the identity word in M.

M ! [ i₁, ..., i_s ] : MonRWS, [ RngIntElt ] -> MonRWSElt

Given a rewrite monoid M defined on r generators and a sequence [i₁, ..., i_s] of integers lying in the range [1, r], construct the word M.i₁ * M.i₂ * ... * M.i_s.

> 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

Arithmetic with Words

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.

(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.

u * v : MonRWSElt, MonRWSElt -> MonRWSElt

Product of the words w and v.

u ^ n : MonRWSElt, RngIntElt -> MonRWSElt

The n-th power of the word w, where n is a positive or zero integer.

u eq v : MonRWSElt, MonRWSElt -> BoolElt

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.

u ne v : MonRWSElt, MonRWSElt -> BoolElt

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.

IsId(w) : MonRWSElt -> BoolElt

IsIdentity(w) : MonRWSElt -> BoolElt

Returns true if the word w is the identity word.

# u : MonRWSElt -> RngIntElt

The length of the word w.

ElementToSequence(u) : MonRWSElt -> [ RngIntElt ]

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.i₁ ... M.i_m, then Q[j] = i_j, for j = 1, ..., m.

> 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

• « Previous
• Up
• Contents
• Index
• Search
• Next »