ThRightNormalForm Class Reference

Defines a representation of a right Garside normal form//. More...

#include <ThRightNormalForm.h>

List of all members.

Public Types

typedef triple< int, int,
list< Permutation > > 
NF
 Presentation of a normal form.

Public Member Functions

 ThRightNormalForm (int rank=0)
 Default constructor (rank specifies the rank of a braid group the form belongs to).
 ThRightNormalForm (int rank, int p, const list< Permutation > &d)
 Constructor (rank specifies the rank of a braid group the form belongs to, p - a power of a half twist, and d - a list of permutations. So the pair (p,d) is a presentation).
 ThRightNormalForm (const NF &tr)
 Constructor (tr specifies a presentation of the normal form).
 ThRightNormalForm (const BraidGroup &G, const Word &w)
 Constructs the normal form of a braid word w.
ThRightNormalFormoperator= (const NF &tr)
 operator NF () const
 Cast operator (returns a representation of a normal form).
bool operator== (const ThRightNormalForm &rep) const
 Compare (check if equal).
bool operator!= (const ThRightNormalForm &rep) const
 Compare (check if not equal).
bool operator< (const ThRightNormalForm &rep) const
 Compare (check if less, performed componentwise).
ThRightNormalForm operator- () const
ThRightNormalForm operator * (const ThRightNormalForm &rep) const
 Multiply two normal forms.
ThRightNormalFormoperator *= (const ThRightNormalForm &rep)
 Multiply a normal form by the other on the right.
int getRank () const
 Get the rank of a corresponding braid group.
int getPower () const
 Get half-twist power.
const list< Permutation > & getDecomposition () const
 Get a list of permutations.
bool isTrivial () const
 Check if a normal form is trivial.
Word getWord () const
 Computes a word represented by a normal form.
Word getShortWord () const
 Computes a "shorter" word represented by a normal form.
pair< bool, ThRightNormalFormareConjugate (const ThRightNormalForm &rep) const
 Check whether two braids are conjugate.
void adjust ()
 Adjust a normal form.
set< ThRightNormalFormcomputeNormalizer () const
 Compute generators of the centralizer of an element.
ThRightNormalForm findSSSRepresentative (ThRightNormalForm &conjugator) const
 Find an element of a super summit set.
ThRightNormalForm findSSSRepresentative () const
void setPower (int p)
 Set a power of a half-twist.
void setDecomposition (const list< Permutation > &d)
 Set a decomposition of a normal form (without any check of "greedy conditions").

Static Public Member Functions

static Permutation getHalfTwistPermutation (int theIndex)
 Construct a half-twist permutation.
static void adjustDecomposition (int rank, int &power, list< Permutation > &decomp)
 Adjust a normal form.
static pair< NF, ThRightNormalFormcycle (const NF &rep)
 Cycle a normal form.
static pair< NF, ThRightNormalFormdecycle (const NF &rep)
 Cycle a normal form.

Private Types

enum  transformationResult { TWO_MULTIPLIERS, ONE_MULTIPLIER, NO_CHANGE }

Private Member Functions

NF inverse () const
 (Low level function) Invert a normal form.
NF multiply (const ThRightNormalForm &rep) const
 (Low level function) Multiply normal forms.

Static Private Member Functions

static pair< NF, ThRightNormalFormfindSSSRepresentative (int rank, const NF &rep)
 (Low level function) Compute super summit set representative.
static transformationResult transform (int theIndex, Permutation &p1, Permutation &p2)
static set< PermutationgetSimpleConjugators (int rank, const NF &rep)
static set< PermutationgetSimpleSummitConjugators (int rank, const NF &rep)
static pair< bool, ThRightNormalFormsssConstructionIteration (int rank, map< NF, NF > &sss_new1, map< NF, NF > &sss_checked1, const map< NF, NF > &sss_new2, const map< NF, NF > &sss_checked2)

Private Attributes

int theRank
 The rank of the braid group (number of strands).
int theOmegaPower
 Power of omega.
list< PermutationtheDecomposition
 Sequence of permutations.


Detailed Description

Defines a representation of a right Garside normal form//.

Definition at line 30 of file ThRightNormalForm.h.


Member Typedef Documentation

typedef triple< int , int , list< Permutation > > ThRightNormalForm::NF
 

Presentation of a normal form.

The first component specifies the rank of a braid group. The second component specifies the power of the half twist. The third component specifies the list of braid permutations.

Definition at line 39 of file ThRightNormalForm.h.


Member Enumeration Documentation

enum ThRightNormalForm::transformationResult [private]
 

Enumerator:
TWO_MULTIPLIERS 
ONE_MULTIPLIER 
NO_CHANGE 

Definition at line 273 of file ThRightNormalForm.h.


Constructor & Destructor Documentation

ThRightNormalForm::ThRightNormalForm int  rank = 0  )  [inline]
 

Default constructor (rank specifies the rank of a braid group the form belongs to).

Default rank value is for map<...> only make sure to provide the argument for this constructor

Definition at line 54 of file ThRightNormalForm.h.

ThRightNormalForm::ThRightNormalForm int  rank,
int  p,
const list< Permutation > &  d
[inline]
 

Constructor (rank specifies the rank of a braid group the form belongs to, p - a power of a half twist, and d - a list of permutations. So the pair (p,d) is a presentation).

There is no check that the pair (p,d) defines a correct normal form representation. If you are not sure if (p,d) is correct apply static function adjustDecomposition first.

Definition at line 65 of file ThRightNormalForm.h.

ThRightNormalForm::ThRightNormalForm const NF tr  )  [inline]
 

Constructor (tr specifies a presentation of the normal form).

Definition at line 71 of file ThRightNormalForm.h.

ThRightNormalForm::ThRightNormalForm const BraidGroup G,
const Word w
 

Constructs the normal form of a braid word w.


Member Function Documentation

void ThRightNormalForm::adjust  )  [inline]
 

Adjust a normal form.

Use this function if there is a possiblitiy that the sequence of permutations does not satisfy the "greedy conditions". Right now this might happen only after use of a constructor ThRightNormalForm (const NF &tr) or, more likely, in function setDecomposition(...). This function uses adjustDecomposition( ... ).

Definition at line 209 of file ThRightNormalForm.h.

References adjustDecomposition(), theDecomposition, theOmegaPower, and theRank.

static void ThRightNormalForm::adjustDecomposition int  rank,
int &  power,
list< Permutation > &  decomp
[static]
 

Adjust a normal form.

Use this function if the triple of arguments does not satisfy "greedy conditions".

Referenced by adjust().

pair<bool,ThRightNormalForm> ThRightNormalForm::areConjugate const ThRightNormalForm rep  )  const
 

Check whether two braids are conjugate.

Very slow function. Checks if super summit sets of two braids contain the same element (i.e., coincide). ... and the super summit sets are typically huge even for decent parameters.

Returns:
- a pair (R,C), where R is a boolean value (true if braids are conjugate, false otherwise), and C is a conjugator (if braids conjugate)

set<ThRightNormalForm> ThRightNormalForm::computeNormalizer  )  const
 

Compute generators of the centralizer of an element.

Very slow function. Function computes the graph with the super summit set of the element as the vertex set. Even for a small rank of a braid group (say 10) and a short braid word (say 100) the super summit set is typically huge.

static pair<NF,ThRightNormalForm> ThRightNormalForm::cycle const NF rep  )  [static]
 

Cycle a normal form.

Operation: $\Delta^s \xi_1 \ldots \xi_{t-1} \xi_t ~\mapsto~ \xi_t \Delta^s \xi_1 \ldots \xi_{t-1}$ .

Returns:
a pair (R,C), where R is the result of a cycling and C is a conjugator (if A is an input then $R = C^{-1} A C$ )

static pair<NF,ThRightNormalForm> ThRightNormalForm::decycle const NF rep  )  [static]
 

Cycle a normal form.

Operation: $\Delta^s \xi_1 \xi_2 \ldots \xi_t ~\mapsto~ \Delta^s \xi_2 \ldots \xi_t \cdot (\Delta^s \xi_1 \Delta^{-s})$ .

Returns:
a pair (R,C), where R is the result of a cycling and C is a conjugator (if A is an input then $R = C^{-1} A C$ )

static pair<NF,ThRightNormalForm> ThRightNormalForm::findSSSRepresentative int  rank,
const NF rep
[static, private]
 

(Low level function) Compute super summit set representative.

ThRightNormalForm ThRightNormalForm::findSSSRepresentative  )  const [inline]
 

Definition at line 226 of file ThRightNormalForm.h.

References theRank.

ThRightNormalForm ThRightNormalForm::findSSSRepresentative ThRightNormalForm conjugator  )  const
 

Find an element of a super summit set.

Function uses cycling and decycling to decrease the canonical length of an element.

const list< Permutation >& ThRightNormalForm::getDecomposition  )  const [inline]
 

Get a list of permutations.

Definition at line 157 of file ThRightNormalForm.h.

References theDecomposition.

static Permutation ThRightNormalForm::getHalfTwistPermutation int  theIndex  )  [inline, static]
 

Construct a half-twist permutation.

Definition at line 160 of file ThRightNormalForm.h.

int ThRightNormalForm::getPower  )  const [inline]
 

Get half-twist power.

Definition at line 155 of file ThRightNormalForm.h.

References theOmegaPower.

int ThRightNormalForm::getRank  )  const [inline]
 

Get the rank of a corresponding braid group.

Definition at line 153 of file ThRightNormalForm.h.

References theRank.

Word ThRightNormalForm::getShortWord  )  const
 

Computes a "shorter" word represented by a normal form.

Try to use the fact that the square of a half twist generates a center. If the power of half-twist is negative then it cancel them with the other permutation braids. After that, for newly obtained permutations computes braid words and concatenates them.

static set<Permutation> ThRightNormalForm::getSimpleConjugators int  rank,
const NF rep
[static, private]
 

static set<Permutation> ThRightNormalForm::getSimpleSummitConjugators int  rank,
const NF rep
[static, private]
 

Word ThRightNormalForm::getWord  )  const
 

Computes a word represented by a normal form.

For each permutation-braid computes a braid-word it represents and, finally, concatenate all the results.

NF ThRightNormalForm::inverse  )  const [private]
 

(Low level function) Invert a normal form.

Referenced by operator-().

bool ThRightNormalForm::isTrivial  )  const [inline]
 

Check if a normal form is trivial.

Definition at line 168 of file ThRightNormalForm.h.

References theDecomposition, and theOmegaPower.

NF ThRightNormalForm::multiply const ThRightNormalForm rep  )  const [private]
 

(Low level function) Multiply normal forms.

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

ThRightNormalForm ThRightNormalForm::operator * const ThRightNormalForm rep  )  const [inline]
 

Multiply two normal forms.

Definition at line 134 of file ThRightNormalForm.h.

References multiply().

ThRightNormalForm& ThRightNormalForm::operator *= const ThRightNormalForm rep  )  [inline]
 

Multiply a normal form by the other on the right.

Definition at line 139 of file ThRightNormalForm.h.

References multiply().

ThRightNormalForm::operator NF  )  const [inline]
 

Cast operator (returns a representation of a normal form).

Definition at line 95 of file ThRightNormalForm.h.

References theDecomposition, theOmegaPower, and theRank.

bool ThRightNormalForm::operator!= const ThRightNormalForm rep  )  const [inline]
 

Compare (check if not equal).

Definition at line 108 of file ThRightNormalForm.h.

References theDecomposition, theOmegaPower, and theRank.

ThRightNormalForm ThRightNormalForm::operator-  )  const [inline]
 

Definition at line 129 of file ThRightNormalForm.h.

References inverse().

bool ThRightNormalForm::operator< const ThRightNormalForm rep  )  const [inline]
 

Compare (check if less, performed componentwise).

Definition at line 116 of file ThRightNormalForm.h.

References theDecomposition, theOmegaPower, and theRank.

ThRightNormalForm& ThRightNormalForm::operator= const NF tr  )  [inline]
 

Definition at line 80 of file ThRightNormalForm.h.

References triple< T1, T2, T3 >::first, triple< T1, T2, T3 >::second, theDecomposition, theOmegaPower, theRank, and triple< T1, T2, T3 >::third.

bool ThRightNormalForm::operator== const ThRightNormalForm rep  )  const [inline]
 

Compare (check if equal).

Definition at line 100 of file ThRightNormalForm.h.

References theDecomposition, theOmegaPower, and theRank.

void ThRightNormalForm::setDecomposition const list< Permutation > &  d  )  [inline]
 

Set a decomposition of a normal form (without any check of "greedy conditions").

Definition at line 255 of file ThRightNormalForm.h.

References theDecomposition.

void ThRightNormalForm::setPower int  p  )  [inline]
 

Set a power of a half-twist.

Definition at line 253 of file ThRightNormalForm.h.

References theOmegaPower.

static pair<bool,ThRightNormalForm> ThRightNormalForm::sssConstructionIteration int  rank,
map< NF, NF > &  sss_new1,
map< NF, NF > &  sss_checked1,
const map< NF, NF > &  sss_new2,
const map< NF, NF > &  sss_checked2
[static, private]
 

static transformationResult ThRightNormalForm::transform int  theIndex,
Permutation p1,
Permutation p2
[static, private]
 


Member Data Documentation

list< Permutation > ThRightNormalForm::theDecomposition [private]
 

Sequence of permutations.

Definition at line 300 of file ThRightNormalForm.h.

Referenced by adjust(), getDecomposition(), isTrivial(), operator NF(), operator!=(), operator<(), operator=(), operator==(), and setDecomposition().

int ThRightNormalForm::theOmegaPower [private]
 

Power of omega.

Definition at line 298 of file ThRightNormalForm.h.

Referenced by adjust(), getPower(), isTrivial(), operator NF(), operator!=(), operator<(), operator=(), operator==(), and setPower().

int ThRightNormalForm::theRank [private]
 

The rank of the braid group (number of strands).

Definition at line 296 of file ThRightNormalForm.h.

Referenced by adjust(), findSSSRepresentative(), getRank(), operator NF(), operator!=(), operator<(), operator=(), and operator==().


The documentation for this class was generated from the following file:
Generated on Mon Feb 27 22:47:19 2006 for CRyptography And Groups (CRAG) by  doxygen 1.4.4