ThLeftNormalForm Class Reference

Defines a representation of a left Garside normal form. More...

#include <ThLeftNormalForm.h>

List of all members.

Public Member Functions

 ThLeftNormalForm (int rank=0)
 Default constructor (rank specifies the rank of a braid group the form belongs to).
 ThLeftNormalForm (const ThLeftNormalForm &rep)
 ThLeftNormalForm (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).
 ThLeftNormalForm (const NF &pr)
 ThLeftNormalForm (const BraidGroup &G, const Word &w)
 Constructs the normal form of a braid word w.
 ThLeftNormalForm (const Permutation &p)
 Construct a positive braid from a permutation.
ThLeftNormalForm & operator= (const ThLeftNormalForm &rep)
 Assignment operator.
ThLeftNormalForm & operator= (const NF &pr)
 Assignment operator.
bool operator== (const ThLeftNormalForm &rep) const
 Compare (check if equal).
bool operator!= (const ThLeftNormalForm &rep) const
 Compare (check if not equal).
bool operator< (const ThLeftNormalForm &rep) const
 Compare (check if less, performed componentwise).
ThLeftNormalForm operator- () const
ThLeftNormalForm operator* (const ThLeftNormalForm &pr) const
 Multiply two normal forms.
ThLeftNormalForm & operator*= (const ThLeftNormalForm &rep)
 Multiply a normal form by the other on the right.
 operator NF () const
 Cast operator (returns a representation of a normal form).
 operator ThRightNormalForm () 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.
ThLeftNormalForm increaseRank (int N) const
 Increase the rank of the braid.
ThLeftNormalForm inverse () const
ThLeftNormalForm multiply (const ThLeftNormalForm &rep) const
Word getWord () const
 Computes a word represented by a normal form.
void adjust ()
triple< ThLeftNormalForm,
ThLeftNormalForm, int > 		findUSSRepresentative () const
 (Low level function) Compute ultra summit set representative.
Permutation getTransport (const ThLeftNormalForm &B, const Permutation &u) const
 (Aux, for USS simple) Compute a transport for *this and B = (*this)^u where p is a permutation.
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 getPullback (const Permutation &s) const
 (Aux, for USS simple) Compute a pullback for *this and B = (*this)^s where s is a permutation.
Permutation getMainPullback (const Permutation &s, int period) const
 (Aux, for USS simple) Compute the main pullback.
int computePeriod () const
 Find a period of USS-elements. If applied not to USS-braid routine will get into an infinite loop.
pair< Permutation, bool > getSimpleUltraConjugator (int period, const Permutation &start) const
 Compute a simple ultra conjugator for starting from "startSymbol".
set< pair< Permutation, bool > > getSimpleUltraConjugators (int period) const
 Compute all simple ultra conjugator for a given braid.
pair< bool, ThLeftNormalForm > areConjugate_uss (const ThLeftNormalForm &nf, int time_sec_bound=999999) const
 Returns true if braids are conjugate.
void setPower (int p)
void setDecomposition (const list< Permutation > &d)
pair< ThLeftNormalForm,
ThLeftNormalForm > 		cycle () const
 Cycle a normal form.
pair< ThLeftNormalForm,
ThLeftNormalForm > 		decycle () const
 Decycle a normal form.
pair< ThLeftNormalForm,
ThLeftNormalForm > 		findSSSRepresentative () const
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.
pair< bool, ThLeftNormalForm > areConjugate (const ThLeftNormalForm &rep) const
 Check whether two braids are conjugate.

Static Public Member Functions

static void adjustDecomposition (int rank, int &power, list< Permutation > &decomp)

Private Types

enum  transformationResult { TWO_MULTIPLIERS, ONE_MULTIPLIER, NO_CHANGE }
typedef triple< int, int, list
< Permutation > > 		NF
 Presentation of a normal form.

Private Member Functions

pair< bool, ThLeftNormalForm > ussConstructionIteration (map< ThLeftNormalForm, pair< ThLeftNormalForm, int > > &uss_new1, map< ThLeftNormalForm, pair< ThLeftNormalForm, int > > &uss_checked1, const map< ThLeftNormalForm, pair< ThLeftNormalForm, int > > &uss_new2, const map< ThLeftNormalForm, pair< ThLeftNormalForm, int > > &uss_checked2) const
 (Aux, USS)
pair< bool, ThLeftNormalForm > ussAddTrajectory (const ThLeftNormalForm &new_elt, const ThLeftNormalForm &new_conjugator, map< ThLeftNormalForm, pair< ThLeftNormalForm, int > > &uss_new1, map< ThLeftNormalForm, pair< ThLeftNormalForm, int > > &uss_checked1, const map< ThLeftNormalForm, pair< ThLeftNormalForm, int > > &uss_new2, const map< ThLeftNormalForm, pair< ThLeftNormalForm, int > > &uss_checked2) const
 (Aux, USS)

Static Private Member Functions

static transformationResult transform (int theIndex, Permutation &p1, Permutation &p2)
static void reverse (NF &pr)

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 left Garside normal form.

Left Garside normal form has the following presentation $ \Delta^\omega \xi_1 \ldots \xi_{t-1} \xi_t $ where $\Delta$ is a half-twist permutation and $\xi_1 \ldots \xi_{t-1} \xi_t$ is a left-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) \supseteq 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 45 of file ThLeftNormalForm.h.

Member Typedef Documentation

typedef triple< int , int , list< Permutation > > ThLeftNormalForm::NF [private]

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 54 of file ThLeftNormalForm.h.

Member Enumeration Documentation

enum ThLeftNormalForm::transformationResult [private]
Enumerator:
TWO_MULTIPLIERS 
ONE_MULTIPLIER 
NO_CHANGE 

Definition at line 440 of file ThLeftNormalForm.h.

Constructor & Destructor Documentation

ThLeftNormalForm::ThLeftNormalForm ( 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 70 of file ThLeftNormalForm.h.

ThLeftNormalForm::ThLeftNormalForm ( const ThLeftNormalForm &  rep  )  [inline]

Definition at line 76 of file ThLeftNormalForm.h.

ThLeftNormalForm::ThLeftNormalForm ( 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 87 of file ThLeftNormalForm.h.

ThLeftNormalForm::ThLeftNormalForm ( const NF &  pr  )  [inline]

Definition at line 92 of file ThLeftNormalForm.h.

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

Constructs the normal form of a braid word w.

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

Construct a positive braid from a permutation.

Definition at line 102 of file ThLeftNormalForm.h.

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

Member Function Documentation

void ThLeftNormalForm::adjust (  )  [inline]

Definition at line 234 of file ThLeftNormalForm.h.

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

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

Referenced by adjust().

pair< bool , ThLeftNormalForm > ThLeftNormalForm::areConjugate ( const ThLeftNormalForm &  rep  )  const

Check whether two braids are conjugate.

Current implementation of this function transforms the left form into the right form and invokes ThRightNormalForm::areConjugate( ... ). 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)
pair< bool , ThLeftNormalForm > ThLeftNormalForm::areConjugate_uss ( const ThLeftNormalForm &  nf,
int  time_sec_bound = 999999 
) const

Returns true if braids are conjugate.

Procedure constructs USS for 2 braids until finds intersections.

int ThLeftNormalForm::computePeriod (  )  const

Find a period of USS-elements. If applied not to USS-braid routine will get into an infinite loop.

pair< ThLeftNormalForm , ThLeftNormalForm > ThLeftNormalForm::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< ThLeftNormalForm , ThLeftNormalForm > ThLeftNormalForm::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< ThLeftNormalForm , ThLeftNormalForm > ThLeftNormalForm::findSSSRepresentative (  )  const
triple< ThLeftNormalForm , ThLeftNormalForm , int > ThLeftNormalForm::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 >& ThLeftNormalForm::getDecomposition (  )  const [inline]

Get a list of permutations.

Definition at line 203 of file ThLeftNormalForm.h.

References theDecomposition.

Referenced by TTPAttack::printStats().

Permutation ThLeftNormalForm::getMainPullback ( const Permutation &  s,
int  period 
) const

(Aux, for USS simple) Compute the main pullback.

int ThLeftNormalForm::getPower (  )  const [inline]

Get half-twist power.

Definition at line 201 of file ThLeftNormalForm.h.

References theOmegaPower.

Referenced by TTPAttack::printStats().

Permutation ThLeftNormalForm::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 ThLeftNormalForm::getRank (  )  const [inline]

Get the rank of a corresponding braid group.

Definition at line 199 of file ThLeftNormalForm.h.

References theRank.

Permutation ThLeftNormalForm::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 > ThLeftNormalForm::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 ThLeftNormalForm::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 > ThLeftNormalForm::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.

pair< Permutation , bool > ThLeftNormalForm::getSimpleUltraConjugator ( int  period,
const Permutation &  start 
) const

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 pair (R,M), where R is the resulting permutation, M is true if R is minimal among all simple ultra conjugators.
set< pair< Permutation , bool > > ThLeftNormalForm::getSimpleUltraConjugators ( int  period  )  const

Compute all simple ultra conjugator for a given braid.

Permutation ThLeftNormalForm::getTransport ( const ThLeftNormalForm &  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 > ThLeftNormalForm::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 ThLeftNormalForm::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.

ThLeftNormalForm ThLeftNormalForm::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.

ThLeftNormalForm ThLeftNormalForm::inverse (  )  const

Referenced by operator-().

bool ThLeftNormalForm::isTrivial (  )  const [inline]

Check if a normal form is trivial.

Definition at line 207 of file ThLeftNormalForm.h.

References theDecomposition, and theOmegaPower.

ThLeftNormalForm ThLeftNormalForm::multiply ( const ThLeftNormalForm &  rep  )  const

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

ThLeftNormalForm::operator NF (  )  const [inline]

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

Definition at line 183 of file ThLeftNormalForm.h.

References theDecomposition, theOmegaPower, and theRank.

ThLeftNormalForm::operator ThRightNormalForm (  )  const

Cast operator.

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

Compare (check if not equal).

Definition at line 145 of file ThLeftNormalForm.h.

References theDecomposition, theOmegaPower, and theRank.

ThLeftNormalForm ThLeftNormalForm::operator* ( const ThLeftNormalForm &  pr  )  const [inline]

Multiply two normal forms.

Definition at line 172 of file ThLeftNormalForm.h.

References multiply().

ThLeftNormalForm& ThLeftNormalForm::operator*= ( const ThLeftNormalForm &  rep  )  [inline]

Multiply a normal form by the other on the right.

Definition at line 176 of file ThLeftNormalForm.h.

References multiply().

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

Definition at line 168 of file ThLeftNormalForm.h.

References inverse().

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

Compare (check if less, performed componentwise).

Definition at line 154 of file ThLeftNormalForm.h.

References theDecomposition, theOmegaPower, and theRank.

ThLeftNormalForm& ThLeftNormalForm::operator= ( const NF &  pr  )  [inline]

Assignment operator.

Definition at line 133 of file ThLeftNormalForm.h.

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

ThLeftNormalForm& ThLeftNormalForm::operator= ( const ThLeftNormalForm &  rep  )  [inline]

Assignment operator.

Definition at line 125 of file ThLeftNormalForm.h.

References theDecomposition, theOmegaPower, and theRank.

bool ThLeftNormalForm::operator== ( const ThLeftNormalForm &  rep  )  const

Compare (check if equal).

static void ThLeftNormalForm::reverse ( NF &  pr  )  [static, private]
void ThLeftNormalForm::setDecomposition ( const list< Permutation > &  d  )  [inline]

Definition at line 348 of file ThLeftNormalForm.h.

References theDecomposition.

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

Definition at line 346 of file ThLeftNormalForm.h.

References theOmegaPower.

static transformationResult ThLeftNormalForm::transform ( int  theIndex,
Permutation &  p1,
Permutation &  p2 
) [static, private]
pair< bool , ThLeftNormalForm > ThLeftNormalForm::ussAddTrajectory ( const ThLeftNormalForm &  new_elt,
const ThLeftNormalForm &  new_conjugator,
map< ThLeftNormalForm, pair< ThLeftNormalForm, int > > &  uss_new1,
map< ThLeftNormalForm, pair< ThLeftNormalForm, int > > &  uss_checked1,
const map< ThLeftNormalForm, pair< ThLeftNormalForm, int > > &  uss_new2,
const map< ThLeftNormalForm, pair< ThLeftNormalForm, int > > &  uss_checked2 
) const [private]

(Aux, USS)

pair< bool , ThLeftNormalForm > ThLeftNormalForm::ussConstructionIteration ( map< ThLeftNormalForm, pair< ThLeftNormalForm, int > > &  uss_new1,
map< ThLeftNormalForm, pair< ThLeftNormalForm, int > > &  uss_checked1,
const map< ThLeftNormalForm, pair< ThLeftNormalForm, int > > &  uss_new2,
const map< ThLeftNormalForm, pair< ThLeftNormalForm, int > > &  uss_checked2 
) const [private]

(Aux, USS)

Member Data Documentation

list< Permutation > ThLeftNormalForm::theDecomposition [private]

Sequence of permutations.

Definition at line 460 of file ThLeftNormalForm.h.

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

int ThLeftNormalForm::theOmegaPower [private]

Power of omega.

Definition at line 457 of file ThLeftNormalForm.h.

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

int ThLeftNormalForm::theRank [private]

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

Definition at line 454 of file ThLeftNormalForm.h.

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

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