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

### `Example: Basic Access (ex-de40ce)`

We illustrate the access operations using the following presentation of $S_4$.

```magma
> 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 $\infty$ is returned.

### `Example: Order Finite (ex-7a9289)`

We construct a threefold cover of $A_6$.

```magma
> 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

```

### `Example: Order Infinite (ex-541f65)`

We construct the 2-generator free abelian group and compute its order. The result `Infinity` indicates that the group has infinite order.

```magma
> 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

```

### `Example: order (ex-2a5004)`

We construct the Weyl group $E_8$ and test whether or not it has finite order.

```magma
> 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ₛ ]: MonRWS, [ RngIntElt ] -> MonRWSElt`

Given a rewrite monoid $M$ defined on $r$ generators and a sequence $[i_1, \cdots, i_s]$ of integers lying in the range $[1, r]$, construct the word $M.i_1*M.i_2* \cdots *M.i_s$.

### `Example: Words (ex-00230f)`

We construct the Fibonacci group $F(2,7)$, and it’s identity.

```magma
> 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 \in 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.

### `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_1 \cdots M.i_m$, then $Q[j] = i_j$, for $j = 1, \ldots, m$.

### `Example: Arithmetic (ex-3c8630)`

We illustrate the word operations by applying them to elements of the Fibonacci monoid $FM(2,5)$.

```magma
> 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

```