Word Class Reference

Class Word (defines a representation of a Word over a group alphabet)//. More...

#include <Word.h>

Inheritance diagram for Word:
ObjectOf< WordRep > ThompsonGroupFNormalForm

List of all members.

Public Types

typedef ConstWordIterator const_iterator
typedef WordIterator iterator
typedef pair< int, int > PII

Public Member Functions

 Word ()
 Default constructor (creates the empty word $w = \varepsilon$).
 Word (const vector< int > &gens)
 Cast constructor. Constructs a word by its presentation (if the word defined in gens is not reduced then it reduces it).
 Word (const list< int > &gens)
 Cast constructor. Constructs a word by its presentation (if the word defined in gens is not reduced then it reduces it).
 Word (int g)
 Cast constructor. Constructs a one letter word.
template<class IntIterator >
 Word (const IntIterator &B, const IntIterator &E)
bool operator< (const Word &wr) const
 Comparison operator.
bool operator> (const Word &wr) const
 Comparison operator.
bool operator== (const Word &wr) const
 Comparison operator.
bool operator!= (const Word &wr) const
 Comparison operator.
Word & operator*= (const Word &w)
 Multiply the word on the right by another word (the result is reduced).
Word operator* (const Word &w) const
 Multiply two words (the result is reduced).
Word & operator^= (const Word &conjugator)
 Conjugate a word by another word (the result is reduced).
Word operator^ (const Word &conjugator) const
Word & operator^= (int power)
 Conjugate a word by another word (the result is reduced).
Word operator^ (int power) const
Word operator- () const
 Invert a word (works the same as inverse).
const_iterator begin () const
const_iterator end () const
iterator begin ()
iterator end ()
Word freelyReduce ()
 Freely reduce a word.
Word freelyReduce (iterator B, iterator E)
 Freely reduce a segment of a word defined by [B,E).
const list< int > & getList () const
 Get a constant representation the word.
list< int > & getList ()
 Get a representation the word. This allows direct manipulation with the representation (which requires caution).
int length () const
 Get the length of the word.
Word & push_back (int gen)
 Multiply the word by a one-letter word defined by gen on the right. The result is being reduced.
Word & push_front (int gen)
 Multiply the word by a one-letter word defined by gen on the left. The result is being reduced.
Word & push_back (const Word &w)
 Multiply the word by a word on the right. The result is being reduced.
Word & push_front (const Word &w)
 Multiply the word by a word on the left. The result is being reduced.
void pop_back ()
 Remove the last symbol.
void pop_front ()
 Remove the first symbol.
int getPower (Word &base) const
 Determines the power of the word (as an element of a free monoid, not as an element of a free group).
bool doesContain (const int &gen) const
 Checks if the word contains a generator given by gen.
void cyclicLeftShift ()
 Shifts the word one position to the left, i.e., $cyclicLeftShift( x_1 x_2 \ldots x_{k-1} x_k ) = x_2 \ldots x_{k-1} x_k x_1 $.
void cyclicRightShift ()
 Shifts the word one position to the right, i.e., $cyclicRightShift( x_1 x_2 \ldots x_{k-1} x_k ) = x_k x_1 x_2 \ldots x_{k-1} $.
Word cyclicallyReduce () const
 Returns the cyclically reduced word.
void cyclicallyReduceWord ()
 Cyclically reduces the Word.
Word cyclicallyReduce (Word &conjugator) const
 Returns the cyclically reduced word and the corresponding conjugator.
void cyclicallyReduceWord (Word &conjugator)
 Cyclically reduces the Word and returns the corresponding conjugator.
Word inverse () const
 Invert the word.
Word cyclicallyPermute (int n) const
 Cyclically permute the word and return the result.
Word & _cyclicallyPermute (int n)
 Cyclically permute the word.
Word initialSegment (int len) const
 Get an initial segment of the word of length len.
Word terminalSegment (int len) const
 Get a terminal segment of the word of length len.
Word segment (int from, int to) const
int exponentSum (const int &gen) const
int isIn (const int &gen) const
Word power (int t) const
template<class ConstIntIterator >
void insert (int pos, ConstIntIterator B, ConstIntIterator E)
 Insert a sequence of generators [B,E) into a word at a position pos.
void insert (int pos, int g)
 Insert a generator g into a word at a position pos.
template<class ConstIntIterator >
void insert (WordIterator it, ConstIntIterator B, ConstIntIterator E)
 Insert a sequence of generators [B,E) into a word before a position it.
void insert (WordIterator it, int g)
 Insert a generator g into a word before a position it.
void replace (WordIterator it, const Generator &g)
 Replace a generator at a position it by g.
void replace (int pos, const Generator &g)
 Replace a generator at a position pos by g.
template<class ConstIntIterator >
void replace (WordIterator it, ConstIntIterator B, ConstIntIterator E)
 Replace a subword of a word starting at a position it by a word [B,E). The length of the word does not increase if [B,E) is longer than the terminal segment of the word [it,end()). In that case terminal symbols of [B,E) are ignored.
Word replaceGenerators (const vector< Word > &images) const
 Returns a word in which generators are replaced by words.
Word minimalEquivalentForm (const set< int > &permutableGenerators, bool inverses, bool cyclicPermutations) const
 Compute the minimal equivalent word.

Static Public Member Functions

static Word randomWord (int n, int wLen)
 Generates a pseudo randomly reduced word of the length wLen over the alphabet $X = \{x_1,\ldots,x_n\}$.
static Word randomWord (int n, int wLenMin, int wLenMax)
 Generates a pseudo randomly reduced word of a length in [wLenMin,wLenMax] and over the alphabet $X = \{x_1,\ldots,x_n\}$.

Private Member Functions

ostream & printOn (ostream &os) const

Friends

ostream & operator<< (ostream &os, const Word &w)
istream & operator>> (istream &is, Word &w)

Detailed Description

Class Word (defines a representation of a Word over a group alphabet)//.

A reduced word is the one which does not involve subwords of the type $x x^{-1}$ or $x^{-1} x$. We represent a reduced word over a group alphabet $X$ as a list of non-trivial integers list< int >. Each generator $x \in X$ is represented by the unique number $n_x$. For each $x \in X$ it is assumed that $n_{x^{-1}} = -n_x$.

Definition at line 38 of file Word.h.

Member Typedef Documentation

typedef ConstWordIterator Word::const_iterator

Definition at line 42 of file Word.h.

typedef WordIterator Word::iterator

Definition at line 43 of file Word.h.

typedef pair< int , int > Word::PII

Definition at line 53 of file Word.h.

Constructor & Destructor Documentation

Word::Word (  )  [inline]

Default constructor (creates the empty word $w = \varepsilon$).

Definition at line 56 of file Word.h.

Word::Word ( const vector< int > &  gens  )  [inline]

Cast constructor. Constructs a word by its presentation (if the word defined in gens is not reduced then it reduces it).

Definition at line 58 of file Word.h.

Word::Word ( const list< int > &  gens  )  [inline]

Cast constructor. Constructs a word by its presentation (if the word defined in gens is not reduced then it reduces it).

Definition at line 60 of file Word.h.

Word::Word ( int  g  )  [inline]

Cast constructor. Constructs a one letter word.

Definition at line 62 of file Word.h.

template<class IntIterator >
Word::Word ( const IntIterator &  B,
const IntIterator &  E 
) [inline]

Definition at line 65 of file Word.h.

Member Function Documentation

Word& Word::_cyclicallyPermute ( int  n  )  [inline]

Cyclically permute the word.

Definition at line 233 of file Word.h.

References ObjectOf< WordRep >::change(), and cyclicallyPermute().

iterator Word::begin (  )  [inline]

Definition at line 145 of file Word.h.

const_iterator Word::begin (  )  const [inline]

Definition at line 143 of file Word.h.

Referenced by BraidDrawPDF::drawCompressedBraid(), WordDraw::drawCompressedBraid(), MaxCommutePartition::findCommutParts(), freelyReduce(), DCBraidReduction::shorten(), and WhiteheadGraph::WhiteheadGraph().

Word Word::cyclicallyPermute ( int  n  )  const [inline]

Cyclically permute the word and return the result.

n>0 => left-shift, n<0 => rigth-shift permute.

Definition at line 227 of file Word.h.

References ObjectOf< Rep >::change().

Referenced by _cyclicallyPermute().

Word Word::cyclicallyReduce ( Word &  conjugator  )  const [inline]

Returns the cyclically reduced word and the corresponding conjugator.

Definition at line 208 of file Word.h.

References ObjectOf< Rep >::change(), and cyclicallyReduce().

Word Word::cyclicallyReduce (  )  const [inline]

Returns the cyclically reduced word.

Definition at line 198 of file Word.h.

References ObjectOf< Rep >::change().

Referenced by cyclicallyReduce(), and cyclicallyReduceWord().

void Word::cyclicallyReduceWord ( Word &  conjugator  )  [inline]

Cyclically reduces the Word and returns the corresponding conjugator.

Definition at line 214 of file Word.h.

References ObjectOf< Rep >::change(), ObjectOf< WordRep >::change(), and cyclicallyReduce().

void Word::cyclicallyReduceWord (  )  [inline]

Cyclically reduces the Word.

Definition at line 205 of file Word.h.

References ObjectOf< WordRep >::change(), and cyclicallyReduce().

void Word::cyclicLeftShift (  )  [inline]

Shifts the word one position to the left, i.e., $cyclicLeftShift( x_1 x_2 \ldots x_{k-1} x_k ) = x_2 \ldots x_{k-1} x_k x_1 $.

Definition at line 193 of file Word.h.

References ObjectOf< WordRep >::change(), and WordRep::cyclicLeftShift().

void Word::cyclicRightShift (  )  [inline]

Shifts the word one position to the right, i.e., $cyclicRightShift( x_1 x_2 \ldots x_{k-1} x_k ) = x_k x_1 x_2 \ldots x_{k-1} $.

Definition at line 195 of file Word.h.

References ObjectOf< WordRep >::change(), and WordRep::cyclicRightShift().

bool Word::doesContain ( const int &  gen  )  const [inline]

Checks if the word contains a generator given by gen.

Definition at line 190 of file Word.h.

References WordRep::doesContain(), and ObjectOf< WordRep >::look().

iterator Word::end (  )  [inline]

Definition at line 146 of file Word.h.

const_iterator Word::end (  )  const [inline]

Definition at line 144 of file Word.h.

Referenced by BraidDrawPDF::drawCompressedBraid(), WordDraw::drawCompressedBraid(), MaxCommutePartition::findCommutParts(), freelyReduce(), DCBraidReduction::shorten(), and WhiteheadGraph::WhiteheadGraph().

int Word::exponentSum ( const int &  gen  )  const [inline]

Definition at line 259 of file Word.h.

References WordRep::exponentSum(), and ObjectOf< WordRep >::look().

Word Word::freelyReduce ( iterator  B,
iterator  E 
)

Freely reduce a segment of a word defined by [B,E).

Word Word::freelyReduce (  )  [inline]

Freely reduce a word.

Definition at line 149 of file Word.h.

References begin(), end(), and freelyReduce().

Referenced by freelyReduce().

list< int >& Word::getList (  )  [inline]

Get a representation the word. This allows direct manipulation with the representation (which requires caution).

Definition at line 166 of file Word.h.

References ObjectOf< WordRep >::change(), and WordRep::getList().

const list< int >& Word::getList (  )  const [inline]

Get a constant representation the word.

Definition at line 164 of file Word.h.

References WordRep::getList(), and ObjectOf< WordRep >::look().

Referenced by ThompsonGroupFNormalForm::operator*(), and ThompsonGroupFNormalForm::operator*=().

int Word::getPower ( Word &  base  )  const [inline]

Determines the power of the word (as an element of a free monoid, not as an element of a free group).

Definition at line 187 of file Word.h.

References ObjectOf< Rep >::change(), WordRep::getPower(), and ObjectOf< WordRep >::look().

Word Word::initialSegment ( int  len  )  const [inline]

Get an initial segment of the word of length len.

Definition at line 239 of file Word.h.

References ObjectOf< Rep >::change().

void Word::insert ( WordIterator  it,
int  g 
)

Insert a generator g into a word before a position it.

template<class ConstIntIterator >
void Word::insert ( WordIterator  it,
ConstIntIterator  B,
ConstIntIterator  E 
) [inline]

Insert a sequence of generators [B,E) into a word before a position it.

void Word::insert ( int  pos,
int  g 
)

Insert a generator g into a word at a position pos.

template<class ConstIntIterator >
void Word::insert ( int  pos,
ConstIntIterator  B,
ConstIntIterator  E 
) [inline]

Insert a sequence of generators [B,E) into a word at a position pos.

Word Word::inverse (  )  const [inline]

Invert the word.

Definition at line 219 of file Word.h.

References ObjectOf< Rep >::change(), WordRep::inverse(), and ObjectOf< WordRep >::look().

int Word::isIn ( const int &  gen  )  const [inline]

Definition at line 263 of file Word.h.

References WordRep::isIn(), and ObjectOf< WordRep >::look().

int Word::length (  )  const [inline]

Get the length of the word.

Definition at line 169 of file Word.h.

References WordRep::length(), and ObjectOf< WordRep >::look().

Referenced by UniformPartition::getPartition(), and WordDraw::WordDraw().

Word Word::minimalEquivalentForm ( const set< int > &  permutableGenerators,
bool  inverses,
bool  cyclicPermutations 
) const

Compute the minimal equivalent word.

permutableGenerators must be positive.

bool Word::operator!= ( const Word &  wr  )  const [inline]

Comparison operator.

Definition at line 88 of file Word.h.

References ObjectOf< Rep >::look(), and ObjectOf< WordRep >::look().

Word Word::operator* ( const Word &  w  )  const [inline]

Multiply two words (the result is reduced).

Reimplemented in ThompsonGroupFNormalForm.

Definition at line 96 of file Word.h.

Word& Word::operator*= ( const Word &  w  )  [inline]

Multiply the word on the right by another word (the result is reduced).

Reimplemented in ThompsonGroupFNormalForm.

Definition at line 91 of file Word.h.

References ObjectOf< WordRep >::change(), and ObjectOf< Rep >::look().

Word Word::operator- (  )  const [inline]

Invert a word (works the same as inverse).

Reimplemented in ThompsonGroupFNormalForm.

Definition at line 128 of file Word.h.

References ObjectOf< Rep >::change(), WordRep::inverse(), and ObjectOf< WordRep >::look().

bool Word::operator< ( const Word &  wr  )  const [inline]

Comparison operator.

The result of comparison of $u = u_1 \ldots u_k$ and $v = v_1 \ldots v_m$ is defined by $ u<v ~\Leftrightarrow~ k<m ~\vee~ ( k=m ~\wedge~ u_i<v_i \mbox{ where $i$ is the smallest index such that $u_i\ne v_i$}) $

Definition at line 82 of file Word.h.

References ObjectOf< Rep >::look(), and ObjectOf< WordRep >::look().

bool Word::operator== ( const Word &  wr  )  const [inline]

Comparison operator.

Reimplemented in ThompsonGroupFNormalForm.

Definition at line 86 of file Word.h.

References ObjectOf< Rep >::look(), and ObjectOf< WordRep >::look().

bool Word::operator> ( const Word &  wr  )  const [inline]

Comparison operator.

Definition at line 84 of file Word.h.

References ObjectOf< Rep >::look(), and ObjectOf< WordRep >::look().

Word Word::operator^ ( int  power  )  const [inline]

Definition at line 120 of file Word.h.

Word Word::operator^ ( const Word &  conjugator  )  const [inline]

Definition at line 108 of file Word.h.

Word& Word::operator^= ( int  power  )  [inline]

Conjugate a word by another word (the result is reduced).

Definition at line 116 of file Word.h.

References ObjectOf< WordRep >::change().

Word& Word::operator^= ( const Word &  conjugator  )  [inline]

Conjugate a word by another word (the result is reduced).

Definition at line 104 of file Word.h.

References ObjectOf< WordRep >::change(), and ObjectOf< Rep >::look().

void Word::pop_back (  )  [inline]

Remove the last symbol.

Definition at line 181 of file Word.h.

References ObjectOf< WordRep >::change(), and WordRep::pop_back().

void Word::pop_front (  )  [inline]

Remove the first symbol.

Definition at line 183 of file Word.h.

References ObjectOf< WordRep >::change(), and WordRep::pop_front().

Word Word::power ( int  t  )  const
ostream& Word::printOn ( ostream &  os  )  const [inline, private]

Definition at line 334 of file Word.h.

References InfiniteAlphabet::defaultAlphabet, and Alphabet::printWord().

Word& Word::push_back ( const Word &  w  ) 

Multiply the word by a word on the right. The result is being reduced.

Word& Word::push_back ( int  gen  )  [inline]

Multiply the word by a one-letter word defined by gen on the right. The result is being reduced.

Definition at line 172 of file Word.h.

References ObjectOf< WordRep >::change(), and WordRep::push_back().

Referenced by DCBraidReduction::shorten().

Word& Word::push_front ( const Word &  w  ) 

Multiply the word by a word on the left. The result is being reduced.

Word& Word::push_front ( int  gen  )  [inline]

Multiply the word by a one-letter word defined by gen on the left. The result is being reduced.

Definition at line 174 of file Word.h.

References ObjectOf< WordRep >::change(), and WordRep::push_front().

static Word Word::randomWord ( int  n,
int  wLenMin,
int  wLenMax 
) [static]

Generates a pseudo randomly reduced word of a length in [wLenMin,wLenMax] and over the alphabet $X = \{x_1,\ldots,x_n\}$.

static Word Word::randomWord ( int  n,
int  wLen 
) [static]

Generates a pseudo randomly reduced word of the length wLen over the alphabet $X = \{x_1,\ldots,x_n\}$.

Referenced by RandomPairGenerator::getFalsePair(), and RandomPairGenerator::getTruePair().

template<class ConstIntIterator >
void Word::replace ( WordIterator  it,
ConstIntIterator  B,
ConstIntIterator  E 
) [inline]

Replace a subword of a word starting at a position it by a word [B,E). The length of the word does not increase if [B,E) is longer than the terminal segment of the word [it,end()). In that case terminal symbols of [B,E) are ignored.

void Word::replace ( int  pos,
const Generator &  g 
)

Replace a generator at a position pos by g.

void Word::replace ( WordIterator  it,
const Generator &  g 
)

Replace a generator at a position it by g.

Word Word::replaceGenerators ( const vector< Word > &  images  )  const

Returns a word in which generators are replaced by words.

Replace generators with the words (images) contained in the vector

Parameters:
images 
Word Word::segment ( int  from,
int  to 
) const [inline]

Definition at line 253 of file Word.h.

References ObjectOf< Rep >::change().

Word Word::terminalSegment ( int  len  )  const [inline]

Get a terminal segment of the word of length len.

Definition at line 246 of file Word.h.

References ObjectOf< Rep >::change().

Friends And Related Function Documentation

ostream& operator<< ( ostream &  os,
const Word &  w 
) [friend]

Reimplemented in ThompsonGroupFNormalForm.

Definition at line 322 of file Word.h.

istream& operator>> ( istream &  is,
Word &  w 
) [friend]

Definition at line 328 of file Word.h.

The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Generated on Mon Sep 26 18:43:53 2011 for CRyptography And Groups (CRAG) by  doxygen 1.6.1