ThLeftNormalForm.h

Go to the documentation of this file.

// Copyright (C) 2005 Alexander Ushakov
// Contents: Definition of class ThLeftNormalForm
//
// Principal Authors: Alexander Ushakov
//
// Revision History:
//


#ifndef _ThLeftNormalForm_h_
#define _ThLeftNormalForm_h_

#include "tuples.h"
#include "Permutation.h"

#include "vector"
#include "list"
using namespace std;


class ThRightNormalForm;
class BraidGroup;
class Word;



//---------------------------------------------------------------------------//
//--------------------------- ThLeftNormalForm ------------------------------//
//---------------------------------------------------------------------------//


class ThLeftNormalForm
{


  typedef triple< int , int , list< Permutation > > NF;
  
  //                                                     //
  //  Constructors:                                      //
  //                                                     //

 public:
  


  ThLeftNormalForm( int rank=0 ) : 
    theRank( rank ) ,
    theOmegaPower( 0 ) ,
    theDecomposition( ) { }
    
    
  ThLeftNormalForm( const ThLeftNormalForm& rep ) : 
    theRank( rep.theRank ),
    theOmegaPower( rep.theOmegaPower ) ,
    theDecomposition( rep.theDecomposition ) { }



  ThLeftNormalForm( int rank , int p , const list< Permutation >& d ) : 
    theRank( rank ),
    theOmegaPower( p ) ,
    theDecomposition( d ) { }

  ThLeftNormalForm( const NF& pr ) : 
    theRank( pr.first ) ,
    theOmegaPower( pr.second ) ,
    theDecomposition( pr.third ) { }

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


  ThLeftNormalForm( const Permutation& p ) {
    theRank = p.size( );
    Permutation omega = Permutation::getHalfTwistPermutation( theRank );
    if( p.isTrivial( ) ) {
      theOmegaPower = 0;
    } else if( p==omega ) {
      theOmegaPower = 1;
    } else {
      theOmegaPower = 0;
      theDecomposition.push_back( p );
    }
  }


  //                                                     //
  //  Operators                                          //
  //                                                     //
public:


  ThLeftNormalForm& operator = ( const ThLeftNormalForm& rep ) {
    theRank = rep.theRank;
    theOmegaPower = rep.theOmegaPower;
    theDecomposition = rep.theDecomposition;
  }
  
  
  ThLeftNormalForm& operator = ( const NF& pr ) {
    theRank = pr.first;
    theOmegaPower = pr.second;
    theDecomposition = pr.third;
  }
  
  
  bool operator==( const ThLeftNormalForm& rep ) const;
  
  
  bool operator != ( const ThLeftNormalForm& rep ) const {
    return 
      theRank!=rep.theRank ||
      theOmegaPower!=rep.theOmegaPower || 
      theDecomposition!=rep.theDecomposition;
  }


  bool operator < ( const ThLeftNormalForm& rep ) const {
    if( theRank<rep.theRank )
      return true;
    if( theRank>rep.theRank )
      return false;
    if( theOmegaPower<rep.theOmegaPower )
      return true;
    if( theOmegaPower>rep.theOmegaPower )
      return false;
    return theDecomposition<rep.theDecomposition;
  }


  // Invert a normal form.  
  ThLeftNormalForm operator - ( ) const { return inverse( ); }
  
  
  ThLeftNormalForm operator * ( const ThLeftNormalForm& pr ) const { return multiply( pr ); }
  

  ThLeftNormalForm& operator *= ( const ThLeftNormalForm& rep ) {
    *this = multiply( rep );
    return *this;
  }

  
  operator NF( ) const { return NF( theRank , theOmegaPower , theDecomposition ); }

  operator ThRightNormalForm( ) const;
  

  
  //                                                     //
  //  Accessors:                                         //
  //                                                     //

 public:
  
  inline int getRank ( ) const { return theRank; }
  inline int getPower( ) const { return theOmegaPower; }
  inline const list< Permutation >& getDecomposition( ) const { return theDecomposition; }
  
  
  bool isTrivial( ) const { 
    return theOmegaPower==0 && theDecomposition.size( )==0;
  }
  

  ThLeftNormalForm increaseRank( int N ) const;

  
  ThLeftNormalForm inverse( ) const;
  ThLeftNormalForm multiply( const ThLeftNormalForm& rep ) const;
  
  

  Word getWord( ) const;
  
  
  static void adjustDecomposition( int rank , int& power , list<Permutation>& decomp );
  
  void adjust( ) { adjustDecomposition( theRank , theOmegaPower , theDecomposition ); }
  

  //                                                     //
  //  USS functions:                                     //
  //                                                     //

 public:


  triple< ThLeftNormalForm , ThLeftNormalForm , int > findUSSRepresentative( ) const;



  Permutation getTransport( const ThLeftNormalForm& B , const Permutation& u ) const;
  

  set< Permutation > getTransports( const Permutation& u , int period ) const;

  

  Permutation getPullback( const Permutation& s ) const;


  /*
    See Proposition 4.8 in Gebhardt, "A New Approach to the Conjugacy Problem in Garside Groups".
    Here we compute \f$p_x(s)\f$.
  */
  Permutation getMainPullback( const Permutation& s , int period ) const;



  int computePeriod( ) const;
  
  

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


  set< pair< Permutation , bool > > getSimpleUltraConjugators( int period ) const;



  pair< bool , ThLeftNormalForm > areConjugate_uss( const ThLeftNormalForm& nf , int time_sec_bound=999999 ) const;
  
  
  //                                                     //
  //  USS functions (internal functions):                //
  //                                                     //

 private:

  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;


  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;

  
  //                                                     //
  //  Modifiers:                                         //
  //                                                     //

 public:
  
  inline void setPower( int p )
    { theOmegaPower = p; }
  inline void setDecomposition( const list< Permutation >& d )
    { theDecomposition = d; }

  //                                                     //
  //  SSS computation:                                   //
  //                                                     //
public:
  

  pair< ThLeftNormalForm , ThLeftNormalForm > cycle( ) const;
  // ThLeftNormalForm cycle( ) const;
  
  

  pair< ThLeftNormalForm , ThLeftNormalForm > decycle( ) const;
  // ThLeftNormalForm decycle( ) const;


  pair< ThLeftNormalForm , ThLeftNormalForm > findSSSRepresentative( ) const;
  
  

  Permutation getSimpleConjugator( const Permutation& start ) const;
  
  

  set< Permutation > getSimpleConjugators( ) const;



  Permutation getSimpleSummitConjugator( const Permutation& start ) const;
  


  set< Permutation > getSimpleSummitConjugators( ) const;



  pair< bool , ThLeftNormalForm > areConjugate( const ThLeftNormalForm& rep ) const;
  
  
  //                                                     //
  //  Internal functions:                                //
  //                                                     //

 private:

  enum transformationResult { TWO_MULTIPLIERS , ONE_MULTIPLIER , NO_CHANGE };
  static transformationResult transform ( int theIndex , Permutation& p1 , Permutation& p2 );

  static void reverse( NF& pr );

  //                                                     //
  //  Data members:                                      //
  //                                                     //

 private:
  
  int theRank;

  int theOmegaPower;

  list< Permutation > theDecomposition;
  
};


ostream& operator << ( ostream& os, const ThLeftNormalForm& rep );


#endif