#include <ThLeftNormalForm.h>
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 | |
typedef triple< int, int, list< Permutation > > | NF |
Presentation of a normal form. | |
enum | transformationResult { TWO_MULTIPLIERS, ONE_MULTIPLIER, NO_CHANGE } |
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. |
Left Garside normal form has the following presentation where
is a half-twist permutation and
is a left-weighted sequence of permutation braids. A sequence of permutation braids is called right-weighted if for any pair
. Here
and
are starting and finishing sets.
Permutations 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
on the left.
Definition at line 45 of file ThLeftNormalForm.h.
|
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. |
|
Definition at line 440 of file ThLeftNormalForm.h. |
|
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. |
|
Definition at line 76 of file ThLeftNormalForm.h. |
|
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. |
|
Definition at line 92 of file ThLeftNormalForm.h. |
|
Constructs the normal form of a braid word w.
|
|
Construct a positive braid from a permutation.
Definition at line 102 of file ThLeftNormalForm.h. References Permutation::getHalfTwistPermutation(), Permutation::isTrivial(), Permutation::size(), theOmegaPower, and theRank. |
|
Definition at line 234 of file ThLeftNormalForm.h. |
|
|
|
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 true if braids are conjugate. Procedure constructs USS for 2 braids until finds intersections. |
|
Find a period of USS-elements. If applied not to USS-braid routine will get into an infinite loop.
|
|
Cycle a normal form.
Operation:
|
|
Decycle a normal form.
Operation:
|
|
|
|
(Low level function) Compute ultra summit set representative.
|
|
Get a list of permutations.
Definition at line 203 of file ThLeftNormalForm.h. |
|
(Aux, for USS simple) Compute the main pullback.
|
|
Get half-twist power.
Definition at line 201 of file ThLeftNormalForm.h. |
|
(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 |
|
Get the rank of a corresponding braid group.
Definition at line 199 of file ThLeftNormalForm.h. |
|
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. |
|
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 |
|
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. |
|
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 |
|
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.
|
|
Compute all simple ultra conjugator for a given braid.
|
|
(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 |
|
(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 |
|
Computes a word represented by a normal form. For each permutation-braid computes a braid-word it represents and, finally, concatenate all the results. |
|
Increase the rank of the braid.
The current braid does not change as an element of |
|
|
|
Check if a normal form is trivial.
Definition at line 207 of file ThLeftNormalForm.h. |
|
|
|
Multiply two normal forms.
Definition at line 172 of file ThLeftNormalForm.h. References multiply(). |
|
Multiply a normal form by the other on the right.
Definition at line 176 of file ThLeftNormalForm.h. References multiply(). |
|
Cast operator (returns a representation of a normal form).
Definition at line 183 of file ThLeftNormalForm.h. |
|
Cast operator.
|
|
Compare (check if not equal).
Definition at line 145 of file ThLeftNormalForm.h. References theDecomposition, theOmegaPower, and theRank. |
|
Definition at line 168 of file ThLeftNormalForm.h. |
|
Compare (check if less, performed componentwise).
Definition at line 154 of file ThLeftNormalForm.h. References theDecomposition, theOmegaPower, and theRank. |
|
Assignment operator.
Definition at line 133 of file ThLeftNormalForm.h. References triple< T1, T2, T3 >::first, triple< T1, T2, T3 >::second, and triple< T1, T2, T3 >::third. |
|
Assignment operator.
Definition at line 125 of file ThLeftNormalForm.h. References theDecomposition, theOmegaPower, and theRank. |
|
Compare (check if equal).
|
|
|
|
Definition at line 348 of file ThLeftNormalForm.h. |
|
Definition at line 346 of file ThLeftNormalForm.h. |
|
|
|
(Aux, USS)
|
|
(Aux, USS)
|
|
Sequence of permutations.
Definition at line 460 of file ThLeftNormalForm.h. Referenced by operator!=(), operator<(), and operator=(). |
|
Power of omega.
Definition at line 457 of file ThLeftNormalForm.h. Referenced by operator!=(), operator<(), operator=(), and ThLeftNormalForm(). |
|
The rank of the braid group (number of strands).
Definition at line 454 of file ThLeftNormalForm.h. Referenced by operator!=(), operator<(), operator=(), and ThLeftNormalForm(). |