---
title: "Basic Operations"
canonical: "https://docs.magma-maths.org/v2.30-1/FinitelyPresentedGroups/MonoidsGivenByRewriteSystems/operation.html"
source: "https://docs.magma-maths.org/v2.30-1/FinitelyPresentedGroups/MonoidsGivenByRewriteSystems/operation.md"
part: "Finitely Presented Groups"
chapter: "Monoids Given by Rewrite Systems"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Finitely Presented Groups", "source": "https://docs.magma-maths.org/v2.30-1/FinitelyPresentedGroups/index-finitely-presented-groups.md"}
  - {"title": "Monoids Given by Rewrite Systems", "source": "https://docs.magma-maths.org/v2.30-1/FinitelyPresentedGroups/MonoidsGivenByRewriteSystems/index-monoids-given-by-rewrite-systems.md"}
prev: {"title": "Construction of a Rewrite Monoid", "source": "https://docs.magma-maths.org/v2.30-1/FinitelyPresentedGroups/MonoidsGivenByRewriteSystems/creation.md"}
next: {"title": "Homomorphisms", "source": "https://docs.magma-maths.org/v2.30-1/FinitelyPresentedGroups/MonoidsGivenByRewriteSystems/homomorphism.md"}
intrinsics:
  - {"name": ".", "signature": "M . i: MonRWS, RngIntElt -> MonRWSElt"}
  - {"name": "Generators", "signature": "Generators(M): MonRWS -> [ MonRWSElt]"}
  - {"name": "NumberOfGenerators", "signature": "NumberOfGenerators(M): MonRWS -> RngIntElt"}
  - {"name": "Ngens", "signature": "Ngens(M): MonRWS -> RngIntElt"}
  - {"name": "Relations", "signature": "Relations(M): MonRWS -> [MonFPRel]"}
  - {"name": "NumberOfRelations", "signature": "NumberOfRelations(M): MonRWS -> RngIntElt"}
  - {"name": "Nrels", "signature": "Nrels(M): MonRWS -> RngIntElt"}
  - {"name": "Ordering", "signature": "Ordering(M): MonRWS -> String"}
  - {"name": "Parent", "signature": "Parent(w): MonRWSElt -> MonRWS"}
  - {"name": "IsConfluent", "signature": "IsConfluent(M): MonRWS -> BoolElt"}
  - {"name": "IsFinite", "signature": "IsFinite(M): MonRWS -> BoolElt, RngIntElt"}
  - {"name": "Order", "signature": "Order(M): MonRWS -> RngIntElt"}
  - {"name": "#", "signature": "# M: MonRWS -> RngIntElt"}
  - {"name": "Identity", "signature": "Identity(M): MonRWS -> MonRWSElt"}
  - {"name": "Id", "signature": "Id(M): MonRWS -> MonRWSElt"}
  - {"name": "!", "signature": "M ! 1: MonRWS, RngIntElt -> MonRWSElt"}
  - {"name": "!", "signature": "M ! [ i₁, ..., iₛ ]: MonRWS, [ RngIntElt ] -> MonRWSElt"}
  - {"name": "*", "signature": "u * v: MonRWSElt, MonRWSElt -> MonRWSElt"}
  - {"name": "^", "signature": "u ^ n: MonRWSElt, RngIntElt -> MonRWSElt"}
  - {"name": "eq", "signature": "u eq v: MonRWSElt, MonRWSElt -> BoolElt"}
  - {"name": "ne", "signature": "u ne v: MonRWSElt, MonRWSElt -> BoolElt"}
  - {"name": "IsId", "signature": "IsId(w): MonRWSElt -> BoolElt"}
  - {"name": "IsIdentity", "signature": "IsIdentity(w): MonRWSElt -> BoolElt"}
  - {"name": "#", "signature": "# u: MonRWSElt -> RngIntElt"}
  - {"name": "ElementToSequence", "signature": "ElementToSequence(u): MonRWSElt -> [ RngIntElt ]"}
  - {"name": "Eltseq", "signature": "Eltseq(u): MonRWSElt -> [ RngIntElt ]"}
examples:
  - "ex-de40ce"
  - "ex-7a9289"
  - "ex-541f65"
  - "ex-2a5004"
  - "ex-00230f"
  - "ex-3c8630"
---

# Basic Operations

## Accessing Monoid Information

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

<a id="operation-operation-monrws-rngintelt-monrwselt"></a>
### `M . i: MonRWS, RngIntElt -> MonRWSElt`

The $i$-th defining generator for $M$.

<a id="function-generators-monrws"></a>
### `Generators(M): MonRWS -> [ MonRWSElt]`

A sequence containing the defining generators for $M$.

<a id="function-numberofgenerators-monrws"></a>
### `NumberOfGenerators(M): MonRWS -> RngIntElt`

<a id="function-ngens-monrws"></a>
### `Ngens(M): MonRWS -> RngIntElt`

The number of defining generators for $M$.

<a id="function-monrws-relations"></a>
### `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$.

<a id="function-numberofrelations-monrws"></a>
### `NumberOfRelations(M): MonRWS -> RngIntElt`

<a id="function-nrels-monrws"></a>
### `Nrels(M): MonRWS -> RngIntElt`

The number of relations in $M$.

<a id="function-ordering-monrws"></a>
### `Ordering(M): MonRWS -> String`

The ordering of $M$.

<a id="function-parent-monrwselt"></a>
### `Parent(w): MonRWSElt -> MonRWS`

The parent monoid $M$ for the word $w$.

<a id="example-ex-de40ce"></a>
### `Example: Accessing Rewrite Monoid Information (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

<a id="function-isconfluent-monrws"></a>
### `IsConfluent(M): MonRWS -> BoolElt`

Returns `true` if $M$ is confluent, `false` otherwise.

<a id="function-isfinite-monrws"></a>
### `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$.

<a id="function-order-monrws"></a>
### `Order(M): MonRWS -> RngIntElt`

<a id="operation-operation-monrws-rngintelt"></a>
### `# 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.

<a id="example-ex-7a9289"></a>
### `Example: Order of a Threefold Cover of A6 (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
```

<a id="example-ex-541f65"></a>
### `Example: Order of a Free Abelian Group (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
```

<a id="example-ex-2a5004"></a>
### `Example: Finiteness of the Weyl Group E8 (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

<a id="function-identity-monrws"></a>
### `Identity(M): MonRWS -> MonRWSElt`

<a id="function-id-monrws"></a>
### `Id(M): MonRWS -> MonRWSElt`

<a id="operation-op-monrws-rngintelt"></a>
### `M ! 1: MonRWS, RngIntElt -> MonRWSElt`

Construct the identity word in $M$.

<a id="operation-op-monrws-rngintelt-2"></a>
### `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$.

<a id="example-ex-00230f"></a>
### `Example: Constructing Words in a Rewrite Monoid (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.

<a id="operation-op-times-monrwselt-monrwselt"></a>
### `u * v: MonRWSElt, MonRWSElt -> MonRWSElt`

Product of the words $w$ and $v$.

<a id="operation-op-pow-monrwselt-rngintelt"></a>
### `u ^ n: MonRWSElt, RngIntElt -> MonRWSElt`

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

<a id="operation-op-eq-monrwselt-monrwselt"></a>
### `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.

<a id="operation-op-ne-monrwselt-monrwselt"></a>
### `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.

<a id="function-isid-monrwselt"></a>
### `IsId(w): MonRWSElt -> BoolElt`

<a id="function-isidentity-monrwselt"></a>
### `IsIdentity(w): MonRWSElt -> BoolElt`

Returns `true` if the word $w$ is the identity word.

<a id="operation-operation-monrwselt-rngintelt"></a>
### `# u: MonRWSElt -> RngIntElt`

The length of the word $w$.

<a id="function-elementtosequence-monrwselt"></a>
### `ElementToSequence(u): MonRWSElt -> [ RngIntElt ]`

<a id="function-eltseq-monrwselt"></a>
### `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$.

<a id="example-ex-3c8630"></a>
### `Example: Word Arithmetic in a Fibonacci Monoid (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
```
