BKLLeftNormalForm.h

Go to the documentation of this file.
00001 // Copyright (C) 2005 Alexander Ushakov
00002 // Contents: Definition of class BKLLeftNormalForm
00003 //
00004 // Principal Authors: Alexander Ushakov
00005 //
00006 // Revision History:
00007 //
00008 
00009 #ifndef _BKLLeftNormalForm_h_
00010 #define _BKLLeftNormalForm_h_
00011 
00012 #include "tuples.h"
00013 #include "Permutation.h"
00014 
00015 // #include "vector"
00016 #include "list"
00017 using namespace std ;
00018 
00019 class BraidGroup;
00020 class Word;
00021 
00022 
00023 //---------------------------------------------------------------------------//
00024 //--------------------------- BKLLeftNormalForm -----------------------------//
00025 //---------------------------------------------------------------------------//
00026 
00027 
00029 
00034 class BKLLeftNormalForm
00035 {
00036   
00037  public:
00038 
00040 
00045   typedef triple< int , int , list< Permutation > > NF;
00046   
00048   //                                                     //
00049   //  Constructors:                                      //
00050   //                                                     //
00052 
00053 
00055   BKLLeftNormalForm( ) :
00056     theOmegaPower( 0 ) { }
00057     
00058     
00060   BKLLeftNormalForm( const BKLLeftNormalForm& bkl ) : 
00061     theRank( bkl.theRank ) ,
00062     theOmegaPower( bkl.theOmegaPower ) ,
00063     theDecomposition( bkl.theDecomposition ) { }
00064     
00066   BKLLeftNormalForm( int rank , int p , const list< Permutation >& d ) : 
00067     theRank( rank ) ,
00068     theOmegaPower( p ) ,
00069     theDecomposition( d ) { }
00070     
00072   BKLLeftNormalForm( const NF& bkl ) : 
00073     theRank( bkl.first ) ,
00074     theOmegaPower( bkl.second ) ,
00075     theDecomposition( bkl.third ) { }
00076 
00077 
00079   BKLLeftNormalForm( const BraidGroup& G , const Word& w );
00080 
00081 
00083   BKLLeftNormalForm& operator = ( const BKLLeftNormalForm& bkl ) {
00084     theRank = bkl.theRank;
00085     theOmegaPower = bkl.theOmegaPower;
00086     theDecomposition = bkl.theDecomposition;
00087   }
00088   
00089   
00091   BKLLeftNormalForm& operator = ( const NF& bkl ) {
00092     theRank = bkl.first;
00093     theOmegaPower = bkl.second;
00094     theDecomposition = bkl.third;
00095   }
00096   
00097   
00099   //                                                     //
00100   //  Operators:                                         //
00101   //                                                     //
00103 
00104  public:
00105 
00106   BKLLeftNormalForm& operator *= ( const BKLLeftNormalForm& bkl );
00107   BKLLeftNormalForm  operator *  ( const BKLLeftNormalForm& bkl ) const;
00108   BKLLeftNormalForm  operator -  ( ) const;
00109 
00110   bool operator ==( const BKLLeftNormalForm& bkl ) const;
00111   bool operator !=( const BKLLeftNormalForm& bkl ) const;
00112   bool operator < ( const BKLLeftNormalForm& bkl ) const;
00113 
00114 
00116   //                                                     //
00117   //  Accessor functions:                                //
00118   //                                                     //
00120 
00121  public:
00122 
00124   int getPower( ) const { return theOmegaPower; }
00126   const list< Permutation >& getDecomposition( ) const { return theDecomposition; }
00127 
00129   operator NF( ) const { return NF( theRank , theOmegaPower , theDecomposition ); }
00130 
00132   bool isTrivial( ) const { return theOmegaPower==0 && theDecomposition.size()==0; }
00133 
00135   static Permutation getTinyTwistPermutation( int theIndex ) {
00136     Permutation result( theIndex );
00137     for( int i=0 ; i<theIndex ; ++i )
00138       result[i] = (i+theIndex-1)%theIndex;
00139     return result;
00140   }
00141 
00142 
00144   Word getWord( ) const;
00145   
00146   
00148   pair< bool , Word > areConjugate( const BKLLeftNormalForm& bkl ) const;
00149   
00151   pair< BKLLeftNormalForm , BKLLeftNormalForm > cycle( ) const;
00153   pair< BKLLeftNormalForm , BKLLeftNormalForm > decycle( ) const;
00155   pair< BKLLeftNormalForm , BKLLeftNormalForm > findSSSRepresentative( ) const;
00156 
00157 
00159   //                                                     //
00160   //  Modifiers:                                         //
00161   //                                                     //
00163 
00164  public:
00165 
00167   inline void setPower( int p )
00168     { theOmegaPower = p; }
00169 
00171   inline void setDecomposition( const list< Permutation >& d )
00172     { theDecomposition = d; }
00173   
00175   //                                                     //
00176   //  Internal functions:                                //
00177   //                                                     //
00179 
00180  private:
00181   
00182   
00184   NF inverse( ) const;
00185   
00186   
00188   NF multiply( const BKLLeftNormalForm& bkl ) const;
00189 
00190 
00192   enum transformationResult { TWO_MULTIPLIERS , ONE_MULTIPLIER , NO_CHANGE };
00194   static transformationResult transform ( int theIndex , Permutation& p1 , Permutation& p2 );
00195 
00196 
00198   static set<Permutation> getSimpleConjugators( const NF& bkl );
00199 
00200 
00202   static set<Permutation> getSimpleSummitConjugators( const NF& bkl );
00203 
00204   
00206   static void adjustDecomposition( int rank ,
00207                                    int& power ,
00208                                    list<Permutation>& decomp );
00209   // this function transforms any (reasonable) decomposition
00210   // to a decomposition of a normal form 
00211 
00213   //                                                     //
00214   //  Data members:                                      //
00215   //                                                     //
00217 
00218  private:
00219 
00221   int theRank;
00222 
00224   int theOmegaPower;
00225 
00227   list< Permutation > theDecomposition;
00228   
00229 };
00230 
00231 
00232 ostream& operator << ( ostream& os, const BKLLeftNormalForm& bkl );
00233 
00234 #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