ThRightNormalForm.h

Go to the documentation of this file.
00001 // Copyright (C) 2005 Alexander Ushakov
00002 // Contents: Definition of class ThRightNormalForm
00003 //
00004 // Principal Authors: Alexander Ushakov
00005 //
00006 // Revision History:
00007 //
00008 
00009 #ifndef _ThRightNormalForm_h_
00010 #define _ThRightNormalForm_h_
00011 
00012 #include "tuples.h"
00013 #include "Permutation.h"
00014 
00015 #include "vector"
00016 #include "list"
00017 using namespace std;
00018 
00019 
00020 class BraidGroup;
00021 class Word;
00022 class ThLeftNormalForm;
00023 
00024 
00025 //---------------------------------------------------------------------------//
00026 //--------------------------- ThRightNormalForm -----------------------------//
00027 //---------------------------------------------------------------------------//
00028 
00030 
00042 class ThRightNormalForm
00043 {
00044 public:
00046 
00051   typedef triple< int , int , list< Permutation > > NF;
00052   
00054   //                                                     //
00055   //  Constructors:                                      //
00056   //                                                     //
00058 
00059 public:
00060   
00062 
00066   ThRightNormalForm( int rank=0 ) : 
00067     theRank( rank ) ,
00068     theOmegaPower( 0 ) ,
00069     theDecomposition( ) { }
00070     
00071     
00073 
00077   ThRightNormalForm( int rank , int p , const list< Permutation >& d ) : 
00078     theRank( rank ),
00079     theOmegaPower( p ) ,
00080     theDecomposition( d ) { }
00081 
00082 
00084   ThRightNormalForm( const NF& tr ) : 
00085     theRank( tr.first ),
00086     theOmegaPower( tr.second ) ,
00087     theDecomposition( tr.third ) { }
00088     
00089     
00091   ThRightNormalForm( const BraidGroup& G , const Word& w );
00092   
00093   
00095   ThRightNormalForm( const Permutation& p ) {
00096     theRank = p.size( );
00097     Permutation omega = Permutation::getHalfTwistPermutation( theRank );
00098     if( p.isTrivial( ) ) {
00099       theOmegaPower = 0;
00100     } else if( p==omega ) {
00101       theOmegaPower = 1;
00102     } else {
00103       theOmegaPower = 0;
00104       theDecomposition.push_back( p );
00105     }
00106   }
00107   
00108   
00110   ThRightNormalForm& operator = ( const NF& tr ) {
00111     theRank = tr.first;
00112     theOmegaPower = tr.second;
00113     theDecomposition = tr.third;
00114     return *this;
00115   }
00116   
00117 
00119   //                                                     //
00120   //  Operators                                          //
00121   //                                                     //
00123 public:
00124 
00125 
00127   operator NF( ) const {
00128     return NF( theRank , theOmegaPower , theDecomposition );
00129   }
00130   
00131   
00133   bool operator == ( const ThRightNormalForm& rep ) const {
00134     return 
00135       theRank==rep.theRank && 
00136       theOmegaPower==rep.theOmegaPower && 
00137       theDecomposition==rep.theDecomposition;
00138   }
00139   
00140   
00142   bool operator != ( const ThRightNormalForm& rep ) const {
00143     return 
00144       theRank!=rep.theRank ||
00145       theOmegaPower!=rep.theOmegaPower || 
00146       theDecomposition!=rep.theDecomposition;
00147   }
00148   
00150   bool operator < ( const ThRightNormalForm& rep ) const {
00151     if( theRank<rep.theRank )
00152       return true;
00153     if( theRank>rep.theRank )
00154       return false;
00155     if( theOmegaPower<rep.theOmegaPower )
00156       return true;
00157     if( theOmegaPower>rep.theOmegaPower )
00158       return false;
00159     return theDecomposition<rep.theDecomposition;
00160   }
00161 
00162 
00163   // Invert a normal form.  
00164   ThRightNormalForm operator - ( ) const {
00165     return inverse( );
00166   }
00167   
00169   ThRightNormalForm operator * ( const ThRightNormalForm& rep ) const {
00170     return multiply( rep );
00171   }
00172   
00174   ThRightNormalForm& operator *= ( const ThRightNormalForm& rep ) {
00175     *this = multiply( rep );
00176     return *this;
00177   }
00178 
00180   operator ThLeftNormalForm( ) const;
00181 
00183   //                                                     //
00184   //  Accessors:                                         //
00185   //                                                     //
00187 
00188 public:
00189   
00191   inline int getRank ( ) const { return theRank; }
00193   inline int getPower( ) const { return theOmegaPower; }
00195   inline const list< Permutation >& getDecomposition( ) const { return theDecomposition; }
00196   
00197 
00199   bool isTrivial( ) const { 
00200     return theOmegaPower==0 && theDecomposition.size( )==0;
00201   }
00202 
00203 
00205 
00209   Word getWord( ) const;
00210 
00211 
00213 
00219   Word getShortWord( ) const;
00220 
00221 
00223 
00226   static ThRightNormalForm randomPositive( int rank , int decomp_length );
00227 
00228 
00230 
00235   ThRightNormalForm increaseRank( int N ) const;
00236   
00237 
00239 
00244   pair< bool , ThRightNormalForm > areConjugate( const ThRightNormalForm& rep ) const;
00245   
00246 
00248 
00251   static void adjustDecomposition( int rank , int& power , list<Permutation>& decomp );
00252 
00254 
00260   void adjust( ) {
00261     adjustDecomposition( theRank , theOmegaPower , theDecomposition );
00262   }
00263 
00265 
00269   set<ThRightNormalForm> computeCentralizer( ) const;
00270 
00271 
00272   
00273   
00275   //                                                     //
00276   //  SSS computation:                                   //
00277   //                                                     //
00279 public:
00280   
00282   /*
00283     Function uses cyclings and decyclings to obtain a representative of SSS.
00284     @return a pair (R,C), where R is the result and C is a conjugator (if A is an input then \f$R = C^{-1} A C\f$)
00285   */
00286   pair< ThRightNormalForm , ThRightNormalForm > findSSSRepresentative( ) const;
00287   
00288   
00290 
00296   pair< ThRightNormalForm , ThRightNormalForm > cycle( ) const;
00297   
00298 
00300 
00306   pair<ThRightNormalForm,ThRightNormalForm> decycle( ) const;
00307   
00308   
00310 
00314   Permutation getSimpleConjugator( const Permutation& start ) const;
00315   
00316   
00318 
00324   set< Permutation > getSimpleConjugators( ) const;
00325   
00326   
00328 
00333   Permutation getSimpleSummitConjugator( const Permutation& start ) const;
00334   
00335 
00336 
00338 
00345   set< Permutation > getSimpleSummitConjugators( ) const;
00346 
00347 
00348 
00349 
00351   //                                                     //
00352   //  USS computation:                                   //
00353   //                                                     //
00355 public:
00356 
00357 
00359 
00363   triple< ThRightNormalForm , ThRightNormalForm , int > findUSSRepresentative( ) const;
00364 
00365   
00367 
00373   triple< Permutation , bool , int > getSimpleUltraConjugator( int period , const Permutation& start );
00374   
00375   
00377   set< pair< Permutation , int > > getSimpleUltraConjugators( int period );
00378   
00379 
00381 
00386   set< Permutation > getTransports( const Permutation& u , int period ) const;
00387   
00388   
00390 
00395   Permutation getTransport( const ThRightNormalForm& B , const Permutation& u ) const;
00396   
00397   
00399 
00404   Permutation getPullback( const Permutation& s ) const;
00405 
00406 
00408 
00410   Permutation getPullback( const Permutation& u , int period ) const;
00411 
00412 
00413 
00414   
00416   //                                                     //
00417   //  Modifiers:                                         //
00418   //                                                     //
00420 public:
00421 
00423   inline void setPower( int p ) { theOmegaPower = p; }
00425   inline void setDecomposition( const list< Permutation >& d ) { theDecomposition = d; }
00426   
00428   //                                                     //
00429   //  Internal functions:                                //
00430   //                                                     //
00432 private:
00433 
00434   
00436   NF inverse( ) const;
00437   
00438   
00440   NF multiply( const ThRightNormalForm& rep ) const;
00441   
00442   
00444   enum transformationResult { TWO_MULTIPLIERS , ONE_MULTIPLIER , NO_CHANGE };
00445   static transformationResult transform ( int theIndex , Permutation& p1 , Permutation& p2 );
00446   
00447 
00449   pair< bool , ThRightNormalForm > sssConstructionIteration( map< ThRightNormalForm , ThRightNormalForm >& sss_new1 ,
00450                                                              map< ThRightNormalForm , ThRightNormalForm >& sss_checked1 ,
00451                                                              const map< ThRightNormalForm , ThRightNormalForm >& sss_new2 ,
00452                                                              const map< ThRightNormalForm , ThRightNormalForm >& sss_checked2 ) const;
00453   
00455   //                                                     //
00456   //  Data members:                                      //
00457   //                                                     //
00459 
00460 private:
00461 
00463   int theRank;
00464 
00466   int theOmegaPower;
00467 
00469   list< Permutation > theDecomposition;
00470   
00471 };
00472 
00473 
00474 ostream& operator << ( ostream& os, const ThRightNormalForm& nf );
00475 
00476 
00477 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

Generated on Mon Sep 26 18:43:45 2011 for CRyptography And Groups (CRAG) by  doxygen 1.6.1