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.
 ThRightNormalForm (const Permutation &p)
 Construct a positive braid from a permutation.
ThRightNormalForm & operator= (const NF &tr)
 Assignment operator.
 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.
ThRightNormalForm & operator*= (const ThRightNormalForm &rep)
 Multiply a normal form by the other on the right.
 operator ThLeftNormalForm () const
 Cast operator.
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.
ThRightNormalForm increaseRank (int N) const
 Increase the rank of the braid.
pair< bool, ThRightNormalForm > areConjugate (const ThRightNormalForm &rep) const
 Check whether two braids are conjugate.
void adjust ()
 Adjust a normal form.
set< ThRightNormalForm > computeCentralizer () const
 Compute generators of the centralizer of an element.
pair< ThRightNormalForm,
ThRightNormalForm > 		findSSSRepresentative () const
 (Low level function) Compute super summit set representative.
pair< ThRightNormalForm,
ThRightNormalForm > 		cycle () const
 Cycle a normal form.
pair< ThRightNormalForm,
ThRightNormalForm > 		decycle () const
 Decycle a normal form.
Permutation getSimpleConjugator (const Permutation &start) const
 Compute the minimal simple conjugator (permutation) starting from "start".
set< Permutation > getSimpleConjugators () const
 Find a list of simple conjugators (permutations) conjugation by which does not decrease the infimum of the element.
Permutation getSimpleSummitConjugator (const Permutation &start) const
 Compute a minimal simple summit conjugator for starting from "start".
set< Permutation > getSimpleSummitConjugators () const
 Find a list of simple conjugators (permutations) conjugation by which does not change infimum and supremum of the given element.
triple< ThRightNormalForm,
ThRightNormalForm, int > 		findUSSRepresentative () const
 (Low level function) Compute ultra summit set representative.
triple< Permutation, bool, int > getSimpleUltraConjugator (int period, const Permutation &start)
 Compute a simple ultra conjugator for starting from "startSymbol".
set< pair< Permutation, int > > getSimpleUltraConjugators (int period)
 Compute all minimal simple ultra conjugators for "rep".
set< Permutation > getTransports (const Permutation &u, int period) const
 (Aux, for USS simple) Compute a set of transports for a pair *this and (*this)^u where p is a permutation.
Permutation getTransport (const ThRightNormalForm &B, const Permutation &u) const
 (Aux, for USS simple) Compute a transport for *this and B = (*this)^u where p is a permutation.
Permutation getPullback (const Permutation &s) const
 (Aux, for USS simple) Compute a pullback for *this and B = (*this)^s where s is a permutation.
Permutation getPullback (const Permutation &u, int period) const
 (Aux, for USS simple) Compute the main pullback for *this and a permutation u
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 ThRightNormalForm randomPositive (int rank, int decomp_length)
 Generate random positive normal form.
static void adjustDecomposition (int rank, int &power, list< Permutation > &decomp)
 Adjust a normal form.

Private Types

enum  transformationResult { TWO_MULTIPLIERS, ONE_MULTIPLIER, NO_CHANGE }
 

The main function which "canonify" a product of two permutations.

More...

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.
pair< bool, ThRightNormalForm > sssConstructionIteration (map< ThRightNormalForm, ThRightNormalForm > &sss_new1, map< ThRightNormalForm, ThRightNormalForm > &sss_checked1, const map< ThRightNormalForm, ThRightNormalForm > &sss_new2, const map< ThRightNormalForm, ThRightNormalForm > &sss_checked2) const
 I think function processes a vertex in a Super Summit Set graph.

Static Private Member Functions

static transformationResult transform (int theIndex, Permutation &p1, Permutation &p2)

Private Attributes

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

Detailed Description

Defines a representation of a right Garside normal form.

Right Garside normal form has the following presentation $ \xi_1 \ldots \xi_{t-1} \xi_t \Delta^\omega$ where $\Delta$ is a half-twist permutation and $\xi_1 \ldots \xi_{t-1} \xi_t$ is a right-weighted sequence of permutation braids. A sequence of permutation braids is called right-weighted if for any pair $\xi_i\xi_{i+1}$ $F(\xi_i) \subseteq S(\xi_{i+1})$. Here $S(\xi) = \{i \mid \xi = x_i \xi' \mbox{ for some permutation } \xi' \}$ and $F(\xi) = \{i \mid \xi = \xi' x_i \mbox{ for some permutation } \xi' \}$ are starting and finishing sets.

Permutations $\xi$ are translated to braids "from right to left". So, you construct a minimal positive braid where points on the right will go to positions defined by $\xi$ on the left.

Definition at line 42 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 51 of file ThRightNormalForm.h.

Member Enumeration Documentation

enum ThRightNormalForm::transformationResult [private]

The main function which "canonify" a product of two permutations.

Enumerator:
TWO_MULTIPLIERS 
ONE_MULTIPLIER 
NO_CHANGE 

Definition at line 444 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 66 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 77 of file ThRightNormalForm.h.

ThRightNormalForm::ThRightNormalForm ( const NF &  tr  )  [inline]

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

Definition at line 84 of file ThRightNormalForm.h.

ThRightNormalForm::ThRightNormalForm ( const BraidGroup &  G,
const Word &  w 
)

Constructs the normal form of a braid word w.

ThRightNormalForm::ThRightNormalForm ( const Permutation &  p  )  [inline]

Construct a positive braid from a permutation.

Definition at line 95 of file ThRightNormalForm.h.

References Permutation::getHalfTwistPermutation(), Permutation::isTrivial(), Permutation::size(), theDecomposition, theOmegaPower, and theRank.

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 260 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::computeCentralizer (  )  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.

pair< ThRightNormalForm , ThRightNormalForm > ThRightNormalForm::cycle (  )  const

Cycle a normal form.

Operation: $ \xi_1 \ldots \xi_{t-1} \xi_t \Delta^s ~\mapsto~ \xi_t \Delta^s \xi_1 \ldots \xi_{t-1} \Delta^s$. Main purpose of the function is to increase the infimum (half twist power) of a normal form. If $n$ cyclings do not increase infimum then the infimum is already maximal.

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$)
pair<ThRightNormalForm,ThRightNormalForm> ThRightNormalForm::decycle (  )  const

Decycle a normal form.

Operation: $ \xi_1 \xi_2 \ldots \xi_t \Delta^s ~\mapsto~ \Delta^s \xi_2 \ldots \xi_t \Delta^s \xi_1$. Main purpose of the function is to decrease the supremum (size of the decomposition) of a normal form. If $n$ decyclings do not decrease supremum then the supremum is already minimal.

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$)
pair< ThRightNormalForm , ThRightNormalForm > ThRightNormalForm::findSSSRepresentative (  )  const

(Low level function) Compute super summit set representative.

triple< ThRightNormalForm , ThRightNormalForm , int > ThRightNormalForm::findUSSRepresentative (  )  const

(Low level function) Compute ultra summit set representative.

Returns:
a triple (R,C,P), where R is the result, C is a conjugator (if A is an input then $R = C^{-1} A C$), and P is the period of the trajectory.
const list< Permutation >& ThRightNormalForm::getDecomposition (  )  const [inline]

Get a list of permutations.

Definition at line 195 of file ThRightNormalForm.h.

References theDecomposition.

int ThRightNormalForm::getPower (  )  const [inline]

Get half-twist power.

Definition at line 193 of file ThRightNormalForm.h.

References theOmegaPower.

Permutation ThRightNormalForm::getPullback ( const Permutation &  u,
int  period 
) const

(Aux, for USS simple) Compute the main pullback for *this and a permutation u

Permutation ThRightNormalForm::getPullback ( const Permutation &  s  )  const

(Aux, for USS simple) Compute a pullback for *this and B = (*this)^s where s is a permutation.

See Definition 4.6 in Gebhardt, "A New Approach to the Conjugacy Problem in Garside Groups". It is important that braids (*this) and (*this)^u belong to their SSS. Also, it is important that (*this) is not a power of $\Delta$ (USS is "trivial" for such elements).

int ThRightNormalForm::getRank (  )  const [inline]

Get the rank of a corresponding braid group.

Definition at line 191 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.

Permutation ThRightNormalForm::getSimpleConjugator ( const Permutation &  start  )  const

Compute the minimal simple conjugator (permutation) starting from "start".

Algorithm 1 from Franco, Gonzalez-Menese, "Conjugacy problem for braid and Garside groups". Conjugating by a simple element does not decrease the infimum of the element.

set< Permutation > ThRightNormalForm::getSimpleConjugators (  )  const

Find a list of simple conjugators (permutations) conjugation by which does not decrease the infimum of the element.

The current version is very simple. For each permutation cycle $(i,i+1)$ it computes the minimal permutation $p$ which starts with $(i,i+1)$ such that conjugation by $p$ does not decrease the infimum of the element and outputs all of such permutations. The output is not guaranteed to be minimal, i.e., some of the permutations can be prefixes of the other.

Permutation ThRightNormalForm::getSimpleSummitConjugator ( const Permutation &  start  )  const

Compute a minimal simple summit conjugator for starting from "start".

Algorithm 4 from Franco, Gonzalez-Menese, "Conjugacy problem for braid and Garside groups". Conjugating by a simple summit element does not decrease the infimum of the element and does not increase the canonical length.

set< Permutation > ThRightNormalForm::getSimpleSummitConjugators (  )  const

Find a list of simple conjugators (permutations) conjugation by which does not change infimum and supremum of the given element.

The current version is very simple. For each permutation cycle $(i,i+1)$ it computes the minimal permutation $p$ which starts with $(i,i+1)$ such that conjugation by $p$ does not decrease the infimum of the element and does not increase the canonical length, and outputs all of such permutations. The output is not guaranteed to be minimal, i.e., some of the permutations can be prefixes of the other.

triple< Permutation , bool , int > ThRightNormalForm::getSimpleUltraConjugator ( int  period,
const Permutation &  start 
)

Compute a simple ultra conjugator for starting from "startSymbol".

Algorithm 4.9 from Gebhardt, "A New Approach to the Conjugacy Problem in Garside Groups". Conjugating by a simple ultra element does not decrease the infimum of the element and does not increase the canonical length. Also, the result of the conjugaction belongs to the USS.

Returns:
a triple (R,M,P), where R is the resulting permutation, M is true if R is minimal, and P is a period of a conjugated braid.
set< pair< Permutation , int > > ThRightNormalForm::getSimpleUltraConjugators ( int  period  ) 

Compute all minimal simple ultra conjugators for "rep".

Permutation ThRightNormalForm::getTransport ( const ThRightNormalForm &  B,
const Permutation &  u 
) const

(Aux, for USS simple) Compute a transport for *this and B = (*this)^u where p is a permutation.

See Proposition 2.1 and Definition 2.4 of Gebhardt "A New Approach to the Conjugacy Problem in Garside Groups". It is important that braids (*this) and B = (*this)^u belong to their SSS. Also, it is important that (*this) is not a power of $\Delta$ (USS is "trivial" for such elements).

set< Permutation > ThRightNormalForm::getTransports ( const Permutation &  u,
int  period 
) const

(Aux, for USS simple) Compute a set of transports for a pair *this and (*this)^u where p is a permutation.

F-set, see Definition 4.2 in Gebhardt, "A New Approach to the Conjugacy Problem in Garside Groups". It is important that braids (*this) and (*this)^u belong to their SSS. Also, it is important that (*this) is not a power of $\Delta$ (USS is "trivial" for such elements).

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.

ThRightNormalForm ThRightNormalForm::increaseRank ( int  N  )  const

Increase the rank of the braid.

The current braid does not change as an element of $F_\infty$. We simply increase the rank and recompute the normal form presentation. If N<theRank then output *this.

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 199 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::operator NF (  )  const [inline]

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

Definition at line 127 of file ThRightNormalForm.h.

References theDecomposition, theOmegaPower, and theRank.

ThRightNormalForm::operator ThLeftNormalForm (  )  const

Cast operator.

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

Compare (check if not equal).

Definition at line 142 of file ThRightNormalForm.h.

References theDecomposition, theOmegaPower, and theRank.

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

Multiply two normal forms.

Definition at line 169 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 174 of file ThRightNormalForm.h.

References multiply().

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

Definition at line 164 of file ThRightNormalForm.h.

References inverse().

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

Compare (check if less, performed componentwise).

Definition at line 150 of file ThRightNormalForm.h.

References theDecomposition, theOmegaPower, and theRank.

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

Assignment operator.

Definition at line 110 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 133 of file ThRightNormalForm.h.

References theDecomposition, theOmegaPower, and theRank.

static ThRightNormalForm ThRightNormalForm::randomPositive ( int  rank,
int  decomp_length 
) [static]

Generate random positive normal form.

Function returns a right normal form with canonical length decomp_length (it can be smaller due to possible cancellations).

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

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

Definition at line 425 of file ThRightNormalForm.h.

References theDecomposition.

void ThRightNormalForm::setPower ( int  p  )  [inline]

Set a power of a half-twist.

Definition at line 423 of file ThRightNormalForm.h.

References theOmegaPower.

pair< bool , ThRightNormalForm > ThRightNormalForm::sssConstructionIteration ( map< ThRightNormalForm, ThRightNormalForm > &  sss_new1,
map< ThRightNormalForm, ThRightNormalForm > &  sss_checked1,
const map< ThRightNormalForm, ThRightNormalForm > &  sss_new2,
const map< ThRightNormalForm, ThRightNormalForm > &  sss_checked2 
) const [private]

I think function processes a vertex in a Super Summit Set graph.

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 469 of file ThRightNormalForm.h.

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

int ThRightNormalForm::theOmegaPower [private]

Power of omega.

Definition at line 466 of file ThRightNormalForm.h.

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

int ThRightNormalForm::theRank [private]

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

Definition at line 463 of file ThRightNormalForm.h.

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

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:51 2011 for CRyptography And Groups (CRAG) by  doxygen 1.6.1