#include <ThRightNormalForm.h>
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. |
Right Garside normal form has the following presentation where
is a half-twist permutation and
is a right-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 42 of file ThRightNormalForm.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 51 of file ThRightNormalForm.h. |
|
The main function which "canonify" a product of two permutations.
Definition at line 444 of file ThRightNormalForm.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 66 of file ThRightNormalForm.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 77 of file ThRightNormalForm.h. |
|
Constructor (tr specifies a presentation of the normal form).
Definition at line 84 of file ThRightNormalForm.h. |
|
Constructs the normal form of a braid word w.
|
|
Construct a positive braid from a permutation.
Definition at line 95 of file ThRightNormalForm.h. References Permutation::getHalfTwistPermutation(), Permutation::isTrivial(), Permutation::size(), theOmegaPower, and theRank. |
|
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. |
|
Adjust a normal form. Use this function if the triple of arguments does not satisfy "greedy conditions". |
|
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.
|
|
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. |
|
Cycle a normal form.
Operation:
|
|
Decycle a normal form.
Operation:
|
|
(Low level function) Compute super summit set representative.
|
|
(Low level function) Compute ultra summit set representative.
|
|
Get a list of permutations.
Definition at line 195 of file ThRightNormalForm.h. |
|
Get half-twist power.
Definition at line 193 of file ThRightNormalForm.h. |
|
(Aux, for USS simple) Compute the main pullback for *this and a permutation u
|
|
(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 191 of file ThRightNormalForm.h. |
|
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. |
|
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 minimal simple ultra conjugators for "rep".
|
|
(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 |
|
(Low level function) Invert a normal form.
|
|
Check if a normal form is trivial.
Definition at line 199 of file ThRightNormalForm.h. |
|
(Low level function) Multiply normal forms.
|
|
Multiply two normal forms.
Definition at line 169 of file ThRightNormalForm.h. References multiply(). |
|
Multiply a normal form by the other on the right.
Definition at line 174 of file ThRightNormalForm.h. References multiply(). |
|
Cast operator (returns a representation of a normal form).
Definition at line 127 of file ThRightNormalForm.h. |
|
Cast operator.
|
|
Compare (check if not equal).
Definition at line 142 of file ThRightNormalForm.h. References theDecomposition, theOmegaPower, and theRank. |
|
Definition at line 164 of file ThRightNormalForm.h. |
|
Compare (check if less, performed componentwise).
Definition at line 150 of file ThRightNormalForm.h. References theDecomposition, theOmegaPower, and theRank. |
|
Assignment operator.
Definition at line 110 of file ThRightNormalForm.h. References triple< T1, T2, T3 >::first, triple< T1, T2, T3 >::second, and triple< T1, T2, T3 >::third. |
|
Compare (check if equal).
Definition at line 133 of file ThRightNormalForm.h. References theDecomposition, theOmegaPower, and theRank. |
|
Generate random positive normal form. Function returns a right normal form with canonical length decomp_length (it can be smaller due to possible cancellations). |
|
Set a decomposition of a normal form (without any check of "greedy conditions").
Definition at line 425 of file ThRightNormalForm.h. |
|
Set a power of a half-twist.
Definition at line 423 of file ThRightNormalForm.h. |
|
I think function processes a vertex in a Super Summit Set graph.
|
|
|
|
Sequence of permutations.
Definition at line 469 of file ThRightNormalForm.h. Referenced by operator!=(), operator<(), and operator==(). |
|
Power of omega.
Definition at line 466 of file ThRightNormalForm.h. Referenced by operator!=(), operator<(), operator==(), and ThRightNormalForm(). |
|
The rank of the braid group (number of strands).
Definition at line 463 of file ThRightNormalForm.h. Referenced by operator!=(), operator<(), operator==(), and ThRightNormalForm(). |