# FreeMonoid S¶

The free monoid on a set S is the monoid of finite products of the form reduce(*, [si ^ ni]) where the si's are in S, and the ni's are nonnegative integers. The multiplication is not commutative. When S is an OrderedSet, then FreeMonoid(S) has order: for two elements x and y the relation x < y holds if either length(x) < length(y) holds or if these lengths are equal and if x is smaller than y w.r.t. the lexicographical ordering induced by S.

1: %

from MagmaWithUnit

*: (%, %) -> %

from Magma

*: (%, S) -> %

x * s returns the product of x by s on the right.

*: (S, %) -> %

s * x returns the product of x by s on the left.

<=: (%, %) -> Boolean if S has OrderedSet

from PartialOrder

<: (%, %) -> Boolean if S has OrderedSet

from PartialOrder

=: (%, %) -> Boolean

from BasicType

>=: (%, %) -> Boolean if S has OrderedSet

from PartialOrder

>: (%, %) -> Boolean if S has OrderedSet

from PartialOrder

^: (%, NonNegativeInteger) -> %

from MagmaWithUnit

^: (%, PositiveInteger) -> %

from Magma

^: (S, NonNegativeInteger) -> %

s ^ n returns the product of s by itself n times.

~=: (%, %) -> Boolean

from BasicType

coerce: % -> OutputForm
coerce: S -> %

from CoercibleFrom S

divide: (%, %) -> Union(Record(lm: %, rm: %), failed)

divide(x, y) returns the left and right exact quotients of x by y, i.e. [l, r] such that x = l * y * r, “failed” if x is not of the form l * y * r.

factors: % -> List Record(gen: S, exp: NonNegativeInteger)

factors(a1\^e1, ..., an\^en) returns [[a1, e1], ..., [an, en]].

first: % -> S

first(x) returns the first letter of x.

hash: % -> SingleInteger

from SetCategory

hashUpdate!: (HashState, %) -> HashState

from SetCategory

hclf: (%, %) -> %

hclf(x, y) returns the highest common left factor of x and y, i.e. the largest d such that x = d a and y = d b.

hcrf: (%, %) -> %

hcrf(x, y) returns the highest common right factor of x and y, i.e. the largest d such that x = a d and y = b d.

latex: % -> String

from SetCategory

leftPower: (%, NonNegativeInteger) -> %

from MagmaWithUnit

leftPower: (%, PositiveInteger) -> %

from Magma

leftRecip: % -> Union(%, failed)

from MagmaWithUnit

length: % -> NonNegativeInteger

length(x) returns the length of x.

lexico: (%, %) -> Boolean if S has OrderedSet

lexico(x, y) returns true iff x is smaller than y w.r.t. the pure lexicographical ordering induced by S.

lquo: (%, %) -> Union(%, failed)

lquo(x, y) returns the exact left quotient of x by y i.e. q such that x = y * q, “failed” if x is not of the form y * q.

lquo: (%, S) -> Union(%, failed)

lquo(x, s) returns the exact left quotient of x by s.

mapExpon: (NonNegativeInteger -> NonNegativeInteger, %) -> %

mapExpon(f, a1\^e1 ... an\^en) returns a1\^f(e1) ... an\^f(en).

mapGen: (S -> S, %) -> %

mapGen(f, a1\^e1 ... an\^en) returns f(a1)\^e1 ... f(an)\^en.

max: (%, %) -> % if S has OrderedSet

from OrderedSet

min: (%, %) -> % if S has OrderedSet

from OrderedSet

mirror: % -> %

mirror(x) returns the reversed word of x.

nthExpon: (%, Integer) -> NonNegativeInteger

nthExpon(x, n) returns the exponent of the n^th monomial of x.

nthFactor: (%, Integer) -> S

nthFactor(x, n) returns the factor of the n^th monomial of x.

one?: % -> Boolean

from MagmaWithUnit

overlap: (%, %) -> Record(lm: %, mm: %, rm: %)

overlap(x, y) returns [l, m, r] such that x = l * m, y = m * r and l and r have no overlap, i.e. overlap(l, r) = [l, 1, r].

recip: % -> Union(%, failed)

from MagmaWithUnit

rest: % -> %

rest(x) returns x except the first letter.

retract: % -> S

from RetractableTo S

retractIfCan: % -> Union(S, failed)

from RetractableTo S

rightPower: (%, NonNegativeInteger) -> %

from MagmaWithUnit

rightPower: (%, PositiveInteger) -> %

from Magma

rightRecip: % -> Union(%, failed)

from MagmaWithUnit

rquo: (%, %) -> Union(%, failed)

rquo(x, y) returns the exact right quotient of x by y i.e. q such that x = q * y, “failed” if x is not of the form q * y.

rquo: (%, S) -> Union(%, failed)

rquo(x, s) returns the exact right quotient of x by s.

sample: %

from MagmaWithUnit

size: % -> NonNegativeInteger

size(x) returns the number of monomials in x.

smaller?: (%, %) -> Boolean if S has Comparable

from Comparable

varList: % -> List S

varList(x) returns the list of variables of x.

BasicType

Comparable if S has Comparable

Magma

MagmaWithUnit

Monoid

OrderedMonoid if S has OrderedSet

OrderedSemiGroup if S has OrderedSet

OrderedSet if S has OrderedSet

PartialOrder if S has OrderedSet

SemiGroup

SetCategory