PlanetMath: reduced word

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (230)
Orphanage
Unclass'd
Unproven (519)
Corrections (16)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

reduced word

(Definition)

Let be a set, and $\left( X\amalg X^{-1} \right)^\ast$ the free monoid with involution on . An element $w\in\left( X\amalg X^{-1} \right)^\ast$ can be uniquely written by juxtaposition of elements of $\left( X\amalg X^{-1} \right)$ , i.e.

$\displaystyle w=w_1w_2...w_n,\ \ w_j\in\left( X\amalg X^{-1} \right),$

then we may improperly say that

is a word on $\left( X\amalg X^{-1} \right)^\ast$ , considering $\left( X\amalg X^{-1} \right)^\ast$ simply as the free monoid on $\left( X\amalg X^{-1} \right)$ .

The word $w=w_1w_2...w_n\in\left( X\amalg X^{-1} \right)^\ast$ is called reduced when $w_j\neq w_{j+1}^{-1}$ for each $j\in\left\{ 1,2,...,n-1 \right\}$ .

Now, starting from a word $w=w_1w_2...w_n\in\left( X\amalg X^{-1} \right)^\ast$ , we can iteratively erase factors $w_j w_{j+1}$ from whenever $w_j= w_{j+1}^{-1}$ , and this iterative process, that we call reduction of , produce a reduced word $w'\in\left( X\amalg X^{-1} \right)^\ast$ . At each step of the process there may be more than one couple of adiacent letters candidate to be erased, so we may ask if different sequences of erasing may produce different reduced words. The following theorem answers the question.

Theorem 1 Each couple of reduction of a same word $w\in\left( X\amalg X^{-1} \right)^\ast$ produce the same reduced word $w'\in\left( X\amalg X^{-1} \right)^\ast$ .

The unique reduced word is called the reduced form of . Thus there exists a well define map $\mathrm{red}:\left( X\amalg X^{-1} \right)^\ast \rightarrow \left( X\amalg X^{-1} \right)^\ast$ that send a word to his reduced form $\mathrm{red}(w)$ .

We can use the map $\mathrm{red}$ to build the free group on in the following way. Let $\mathrm{FG}(X)=\mathrm{red}\left( \left( X\amalg X^{-1} \right)^+ \right)$ be the set of reduced words on $\left( X\amalg X^{-1} \right)$ , i.e.

$\displaystyle \mathrm{FG}(X)=\mathrm{red}\left( \left( X\amalg X^{-1} \right)^+... ...\left\{ w\in\left( X\amalg X^{-1} \right)^+\,\vert\,w=\mathrm{red}(u) \right\}.$

Note that $\mathrm{red}\left( \left( X\amalg X^{-1} \right)^\ast \right)=\mathrm{red}\left( \left( X\amalg X^{-1} \right)^+ \right)$ , being that $\mathrm{red}(xx^{-1})=\varepsilon$ , where $\varepsilon$ denotes the empty word. Now, we define a product $\cdot$ on $\mathrm{FG}(X)$ that makes it a group: given $v,w\in\mathrm{FG}(X)$ we define

$\displaystyle v\cdot w=\mathrm{red}(vw),$

i.e. $v\cdot w$ is the reduced form of the juxtaposition of the words

and

. The we have the following result.

Theorem 2 $\mathrm{FG}(X)$ with the product $\cdot$ is a group. Moreover, it is the free group on , in the sense that it solves the following universal problem: given a group and a map $\Phi:X\rightarrow G$ , a group homomorphism $\overline\Phi:\mathrm{FG}(X)\rightarrow G$ exists such that the following diagram commutes:

$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ & X \ar[r]^{\iota} \ar[d]_{\Phi} & \mathrm{FG}(X) \ar[dl]^{\overline{\Phi}} \ & G & } } \end{xy}$

where $\iota:X\rightarrow \mathrm{FG}(X)$ is the inclusion map.

It is well known from universal algebra that $\mathrm{FG}(X)$ is unique up to isomorphisms. With this construction, the map $\mathrm{red}:\left( X\amalg X^{-1} \right)^+\rightarrow\mathrm{FG}(X)$ [resp. $\mathrm{red}:\left( X\amalg X^{-1} \right)^\ast \rightarrow\mathrm{FG}(X)$ ] is the quotient projection from the free semigroup with involution on

[resp. the free monoid with involution on

] and the free group on

Bibliography

1: J.M. Howie, Fundamentals of Semigroup Theory, Oxford University Press, Oxford, 1991.
2: R. Lyndon and P. Schupp, Combinatorial Group Theory, Springer-Verlag, 1977.
3: N. Petrich, Inverse Semigroups, Wiley, New York, 1984.

"reduced word" is owned by Mazzu.

(view preamble)

Also defines:

reduced word, reduced form, reduction

Keywords:

free semigroup with involution, free monoid with involution, free group

Attachments:: cyclically reduced (Definition) by CWoo

Log in to rate this entry.
(view current ratings)

Cross-references: free semigroup with involution, projection, quotient, isomorphisms, universal algebra, inclusion map, diagram, group homomorphism, universal, group, product, empty word, free group, map, sequences, factors, free monoid, word, juxtaposition, free monoid with involution
There are 15 references to this entry.

This is version 13 of reduced word, born on 2006-08-24, modified 2006-08-24.
Object id is 8289, canonical name is ReducedWord.
Accessed 2533 times total.

Classification:

AMS MSC:

20E05 (Group theory and generalizations :: Structure and classification of infinite or finite groups :: Free nonabelian groups)

Pending Errata and Addenda

None.[ View all 1 ]

Discussion

forum policy

No messages.

Interact