[Next][Prev] [Right] [Left] [Up] [Index] [Root] 
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)
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 ... M.i_m, then Q[j] = i_j, for
j = 1, ..., m.





Example MonRWS_Arithmetic (H15E3)

We illustrate the word operations by applying them to 
elements of the Fibonacci group F(2, 5).





> FM<a,A,b,B,c,C,d,D,e,E> := FreeMonoid(10);
> 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,
>         a*b=c, b*c=d, c*d=e, d*e=a, e*a=b>;
> M<a,A,b,B,c,C,d,D,e,E> := RWSMonoid(Q);
> print a*b*c*d;
E
> print (c*d)^4 eq a;
true
> print IsIdentity(a*A);
true
> print #(d*a*(B*b)^10);
1






 [Next][Prev] [Right] [Left] [Up] [Index] [Root]