Operations on the Set of Elements

Subsections

• Order Functions
• Set Operations
• Membership and Equality

Order Functions

Order(M) : MonRWS -> RngIntElt

# M : MonRWS -> RngIntElt

The order of the monoid M as an integer. If the order of M is known to be infinite Infinity is returned.

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.

Example MonRWS_Order (H15E5)

(1)

We construct the 2-generator free abelian group and compute its order. The result of 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

(2)

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

Set Operations

Random(M, n) : MonRWS, RngIntElt -> MonRWSElt

A random word of length at most n in the generators of M.

Random(M) : MonRWS -> MonRWSElt

A random word (of length at most the order of M) in the generators of M.

Representative(M) : MonRWS -> MonRWSElt

Rep(M) : MonRWS -> MonRWSElt

An element chosen from M.

Set(M, a, b) : MonRWS, RngIntElt, RngIntElt -> SetEnum

    Search: MonStgElt                   Default: "DFS"

Create the set of words, w, in M with a <= length(w) <= b. If Search is set to "DFS" (depth-first search) then words are enumerated in lexicographical order. If Search is set to "BFS" (breadth-first-search) then words are enumerated in lexicographical order for each individual length (i.e. in short-lex order). Depth-first-search is marginally quicker. Since the result is a set the words may not appear in the resultant set in the search order specified (although internally they will be enumerated in this order).

Set(M) : MonRWS -> SetEnum

    Search: MonStgElt                   Default: "DFS"

Create the set of words that is the carrier set of M. If Search is set to "DFS" (depth-first search) then words are enumerated in lexicographical order. If Search is set to "BFS" (breadth-first-search) then words are enumerated in lexicographical order for each individual length (i.e. in short-lex order). Depth-first-search is marginally quicker. Since the result is a set the words may not appear in the resultant set in the search order specified (although internally they will be enumerated in this order).

Seq(M, a, b) : MonRWS, RngIntElt, RngIntElt -> SeqEnum

    Search: MonStgElt                   Default: "DFS"

Create the sequence S of words, w, in M with a <= length(w) <= b. If Search is set to "DFS" (depth-first search) then words will appear in S in lexicographical order. If Search is set to "BFS" (breadth-first-search) then words will appear in S in lexicographical order for each individual length (i.e. in short-lex order). Depth-first-search is marginally quicker.

Seq(M) : MonRWS -> SeqEnum

    Search: MonStgElt                   Default: "DFS"

Create a sequence S of words from the carrier set of M. If Search is set to "DFS" (depth-first search) then words will appear in S in lexicographical order. If Search is set to "BFS" (breadth-first-search) then words will appear in S in lexicographical order for each individual length (i.e. in short-lex order). Depth-first-search is marginally quicker.

Example MonRWS_Set (H15E6)

> FM<a,A,b,B,c,C,d,D,e,E,f,F> := FreeMonoid(12);
> 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,
>         a*C*A*d=1, b*f*B*E=1, c*e*C*D=1, d*F*D*a=1,
>         e*b*E*A=1, f*C*F*B=1>;
> M<a,A,b,B,c,C,d,D,e,E,f,F> := RWSMonoid(Q);
> print Representative(M);
Id(M)
> print Random(M);
d
> print Random(M, 5);
a * c * e
> Set(M);
{ a * d * b, a * b, a * b * e, a * c, a * d, d * b, b * e, a * b * a, a * b * d,
b * a, a * c * e, Id(M), b * d, c * e, e, f, a, a * e, b, c, a * f, d }
> Seq(M : Search := "BFS");
[ Id(M), a, b, c, d, e, f, a * b, a * c, a * d, a * e, a * f, b * a, b * d, b * 
e, c * e, d * b, a * b * a, a * b * d, a * b * e, a * c * e, a * d * b ]

Membership and Equality

w in M : MonRWSElt, MonRWS -> BoolElt

Given a word w and a rewrite monoid M, return true if w is an element of M, false otherwise.

w notin M : MonRWSElt, MonRWS -> BoolElt

Given a word w and a rewrite monoid M, return true if w is not an element of M, false otherwise.

S subset M : { MonRWSElt }, MonRWS -> BoolElt

Given a rewrite monoid M and a set (or sequence) S of words return true if every member of S is an element of M, false otherwise.

S notsubset M : { MonRWSElt }, MonRWS -> BoolElt

Given a rewrite monoid M and a set (or sequence) S of words return true if any member of S is not an element of M, false otherwise.