Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

/magnus/back_end/AProducts/include/HNNExtOfORGroup.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: HNNExtOfORGroup.h,v 1.5 1999/11/23 20:18:46 bormotov Exp $
00003  */
00004 
00005 // Copyright (C) 1996 The New York Group Theory Cooperative
00006 // See magnus/doc/COPYRIGHT for the full notice.
00007 
00008 // Contents:  Interface of class HNNExtOfORGroup.
00009 //            
00010 // Principal Author: Dmitry Pechkin
00011 //
00012 // Status: in progress.
00013 //
00014 // Revision History:
00015 //
00016 // * 03/99 Dmitry B. changed status from protected to public for
00017 //         Generator HNNExtOfORGroupGeneric::stableLetter( ) const;
00018 //
00019 // TO DO:
00020 //
00021 //
00022 
00023 #ifndef __HNN_EXTENSION_OF_ORGROUP_H_
00024 #define __HNN_EXTENSION_OF_ORGROUP_H_
00025 
00026 #include "Set.h"
00027 #include "Vector.h"
00028 #include "VectorPtr.h"
00029 #include "OneRelatorGroup.h"
00030 #include "SubgroupOfOneRelatorGroup.h"
00031 #include "OneRelatorGroupWithTorsion.h"
00032 // class SubgroupOfOneRelatorGroup;
00033 
00034 class HNNExtOfORGroupGeneric
00035 {
00036 
00037 public:
00038 
00039   enum NumberOfSubgroup { A = 0, B = 1 };
00040   enum Pinch { UP, DOWN };
00041 
00042 //  Constructors: 
00043 
00044   HNNExtOfORGroupGeneric( const OneRelatorGroup& G, const Chars& stableGenName,
00045                           const ORGSubgroup& A, const ORGSubgroup& B);
00046   // stable generator has biggest order in constructing group = lastGenOf(G)+1.
00047 
00048   
00049   HNNExtOfORGroupGeneric( const HNNExtOfORGroupGeneric& H );
00050 
00051   virtual ~HNNExtOfORGroupGeneric( );
00052 
00053   HNNExtOfORGroupGeneric& operator=( const HNNExtOfORGroupGeneric& H );
00054 
00055 
00056 //  Accessors/modifiers:
00057 
00058   virtual const ORGSubgroup& subgroup(NumberOfSubgroup i) const { 
00059     return *subgroups[i]; 
00060   }
00061 
00062   const OneRelatorGroup& basisGroup( ) const { return *theBasisGroup; }
00063 
00064   FPGroup getPresentation( ) const;
00065 
00066   Chars nameOfStableGenerator( ) const { return theNameOfStableGenerator; }
00067 
00068 //  Methods which deal with group elements:
00069 
00070   virtual Trichotomy wordProblem( const Word& w ) const = 0;
00071 
00072   int lengthOf( const Word& w ) const;
00073   int lengthOf( const VectorOf<Word>& deco ) const;
00074 
00075   VectorOf<Word> decompositionOf( const Word& w ) const;
00076   VectorOf<Word> reducedDecompositionOf( const Word& w ) const;
00077   VectorOf<Word> normalDecompositionOf( const Word& w ) const;
00078 
00079   VectorOf<Word> cyclicallyReducedDecompositionOf( const Word& w, Word& conj )
00080     const;
00081   // It returns a decomposition w1 of w and a conjugator `conj' such that
00082   // w1 = w ^ conj.
00083 
00084   //  static Word compose( const VectorOf<Word>& deco );
00085 
00086   Word mappingFromSubgroup( NumberOfSubgroup subgrp, const Word& w ) const;
00087 
00088   ProductOfRelatorConjugates mappingDecompositionOf( 
00089     const NumberOfSubgroup& S, const Word& w, const Word& wInSBasis, 
00090     const Word& tail ) const;
00091 
00092   Generator stableLetter( ) const {
00093     return theBasisGroup->numberOfGenerators() + 1;
00094   }
00095 
00096 
00097 //  Standard comparison operators:  
00098 
00099   virtual bool operator == ( const HNNExtOfORGroupGeneric& G ) const;
00100 
00101   friend inline ostream& operator << ( ostream& ostr, 
00102                                        const HNNExtOfORGroupGeneric& H ) 
00103   {
00104     H.printOn( ostr );
00105     return ostr;
00106   }
00107 
00108 
00109 protected:
00110 
00111   struct PinchStruct {
00112     Pinch type;
00113     int number;
00114     Word word;
00115   };
00116 
00117   ///////////////////////////////////////////////////////
00118   //                                                   //
00119   //  Debugging stuff                                  //
00120   //                                                   //
00121   ///////////////////////////////////////////////////////
00122 
00123 
00124   ///////////////////////////////////////////////////////
00125   //                                                   //
00126   //  I/O routines:                                    //
00127   //                                                   //
00128   ///////////////////////////////////////////////////////
00129 
00130   void printOn( ostream& ostr ) const;
00131 
00132   void printDecomposition( ostream& ostr, const VectorOf<Word>& deco ) const;
00133 
00134   //  virtual HNNExtOfORGroupGeneric* readFrom( istream& istr, 
00135   //                                            Chars& errMesg ) const;
00136 
00137   virtual void debugPrint( ostream& ostr ) const;
00138 
00139   ///////////////////////////////////////////////////////
00140   //                                                   //
00141   //  IPC tools:                                       //
00142   //                                                   //
00143   ///////////////////////////////////////////////////////
00144 
00145   virtual void write( ostream& ostr ) const;
00146   virtual void read( istream& istr );
00147 
00148   ///////////////////////////////////////////////////////
00149   //                                                   //
00150   //  Private helper stuff:                            //
00151   //                                                   //
00152   ///////////////////////////////////////////////////////
00153 
00154   int powerOfStableGen(int component, const VectorOf<Word>& deco ) const;
00155 
00156   bool suspectPinch(int component, const VectorOf<Word>& deco ) const;
00157 
00158   bool abelianizationTest( const PinchStruct& pinch, 
00159                            const VectorOf<int>& powersOfGens,
00160                            const VectorOf<bool>& subgroupGens ) const;
00161 
00162   PinchStruct formPinch(int component, const VectorOf<Word>& deco) const;
00163 
00164   ///////////////////////////////////////////////////////
00165   //                                                   //
00166   //  Debugging stuff                                  //
00167   //                                                   //
00168   ///////////////////////////////////////////////////////
00169 
00170   int unusedGenerators( const Word& test, VectorOf<Word>& toNewGens,
00171                         VectorOf<Word>& toOldGens ) const;
00172 
00173   void init( const HNNExtOfORGroupGeneric& H );
00174 
00175   // Data members:
00176 
00177   OneRelatorGroup *theBasisGroup;
00178   Chars theNameOfStableGenerator;
00179   ORGSubgroup *subgroups[2];
00180 };
00181 
00182 
00183 class HNNExtOfORGroup : public HNNExtOfORGroupGeneric
00184 {
00185 
00186 public:
00187 
00188 //  Constructors: 
00189 
00190   HNNExtOfORGroup( const OneRelatorGroup& G,
00191                    const Chars& stableGenName,
00192                    const SubgroupOfOneRelatorGroup& A,
00193                    const SubgroupOfOneRelatorGroup& B);
00194   // stable generator has biggest order in constructing group = lastGenOf(G)+1.
00195 
00196 //  Accessors/modifiers:
00197 
00198   // SubgroupOfOneRelatorGroup subgroup(int i) const { return subgroups[i]; }
00199   // OneRelatorGroup getBasisGroup( ) const { return theBasisGroup; }
00200   // FPGroup getPresentation( ) const;
00201   // Chars nameOfStableGenerator( ) const { return theNameOfStableGenerator; }
00202 
00203 //  Methods which deal with group elements:
00204 
00205   Trichotomy wordProblem( const Word& test ) const;
00206 
00207   Trichotomy wordProblem( const Word& test, bool keepDetails,
00208     ProductOfRelatorConjugates& productOfRelatorConjugates ) const;
00209 
00210   //  int lengthOf( const Word& w ) const;
00211   //  int lengthOf( const VectorOf<Word>& deco ) const;
00212   //  VectorOf<Word> decompositionOf( const Word& w ) const;
00213   //  VectorOf<Word> reducedDecompositionOf( const Word& w ) const;
00214   //  VectorOf<Word> normalDecompositionOf( const Word& w ) const;
00215   //  VectorOf<Word> cyclicallyReducedDecompositionOf( const Word& w, 
00216   //                                                   Word& conj ) const;
00217   //  Word mappingFromSubgroup( int subgrp, const Word& w ) const;
00218 
00219   VectorOf<Word> reducedDecompositionOf( const Word& w, bool keepDetails,
00220     ProductOfRelatorConjugates& productOfRelatorConjugates ) const;
00221 
00222 
00223 //  Standard comparison operators:  
00224 
00225   //  bool operator == ( const HNNExtOfORGroup& G ) const;
00226 
00227 
00228   ///////////////////////////////////////////////////////
00229   //                                                   //
00230   //  Debugging stuff                                  //
00231   //                                                   //
00232   ///////////////////////////////////////////////////////
00233 
00234 
00235   ///////////////////////////////////////////////////////
00236   //                                                   //
00237   //  I/O routines:                                    //
00238   //                                                   //
00239   ///////////////////////////////////////////////////////
00240 
00241   //  void printOn( ostream& ostr ) const;
00242   //  void printDecomposition( ostream& ostr, const VectorOf<Word>& deco )
00243   //    const;
00244   //  HNNExtOfORGroup* readFrom( istream& istr, Chars& errMesg ) const;
00245   //  void debugPrint( ostream& ostr ) const;
00246 
00247   ///////////////////////////////////////////////////////
00248   //                                                   //
00249   //  IPC tools:                                       //
00250   //                                                   //
00251   ///////////////////////////////////////////////////////
00252 
00253   //  void write( ostream& ostr ) const;
00254   //  void read( istream& istr );
00255 
00256 private:
00257 
00258   ///////////////////////////////////////////////////////
00259   //                                                   //
00260   //  Private helper stuff:                            //
00261   //                                                   //
00262   ///////////////////////////////////////////////////////
00263 
00264   //  int powerOfStableGen(int component, const VectorOf<Word>& deco ) const;
00265   //  bool suspectPinch(int component, const VectorOf<Word>& deco ) const;
00266   //  bool abelianizationTest( const Pinch& pinch, 
00267   //                           const VectorOf<int>& powersOfGens,
00268   //                           const VectorOf<bool>& subgroupGens ) const;
00269   //  Pinch formPinch(int component, const VectorOf<Word>& deco) const;
00270 
00271 
00272 protected:
00273 
00274   ///////////////////////////////////////////////////////
00275   //                                                   //
00276   //  Debugging stuff                                  //
00277   //                                                   //
00278   ///////////////////////////////////////////////////////
00279 
00280   //  Generator stableLetter( ) const;
00281 
00282   int unusedGenerators( const Word& test, VectorOf<Word>& toNewGens,
00283                         VectorOf<Word>& toOldGens ) const;
00284 
00285  
00286 
00287 protected:
00288 
00289   // Data members:
00290 
00291   //  OneRelatorGroup theBasisGroup;
00292   //  Chars theNameOfStableGenerator;
00293   //  VectorPtrOf<SubgroupOfOneRelatorGroup> subgroups;
00294   //  static const int A = 0; // number of subgroup A.
00295   //  static const int B = 1; // number of subgroup B.
00296 };
00297 
00298 
00299 class HNNExtOfORGroupWithTorsion : public HNNExtOfORGroupGeneric
00300 {
00301 
00302 public:
00303 
00304 //  Constructors: 
00305 
00306   HNNExtOfORGroupWithTorsion( const OneRelatorGroupWithTorsion& G,
00307                               const Chars& stableGenName,
00308                               const SubgroupOfORGroupWithTorsion& A,
00309                               const SubgroupOfORGroupWithTorsion& B );
00310   // stable generator has biggest order in constructing group = lastGenOf(G)+1.
00311 
00312 
00313   //  Accessors/modifiers:
00314 
00315   // Inherited from HNNExtOfORGroup:
00316   //   SubgroupOfOneRelatorGroup subgroup(int i) const { return subgroups[i]; }
00317   //   OneRelatorGroupWithTorsion getBasisGroup( ) const;
00318   //   FPGroup getPresentation( ) const;
00319   //   Chars nameOfStableGenerator( ) const;
00320 
00321 //  Methods which deal with group elements:
00322 
00323   Trichotomy wordProblem( const Word& test ) const;
00324 
00325   Trichotomy conjugacyProblem( const Word& u, const Word& v, 
00326                                Word& conjugator ) const;
00327   // 
00328 
00329   //  int lengthOf( const Word& w ) const;
00330   //  int lengthOf( const VectorOf<Word>& deco ) const;
00331 
00332   //  VectorOf<Word> decompositionOf( const Word& w ) const;
00333   //  Word mappingFromSubgroup( int subgrp, const Word& w ) const;
00334   //  bool operator == ( const HNNExtOfORGroup& G ) const;
00335 
00336   Trichotomy maximalRoot( const Word& w, Word& root, int& power ) const;
00337 
00338 //private:
00339 
00340 
00341   ///////////////////////////////////////////////////////
00342   //                                                   //
00343   //  Debugging stuff                                  //
00344   //                                                   //
00345   ///////////////////////////////////////////////////////
00346 
00347 
00348   ///////////////////////////////////////////////////////
00349   //                                                   //
00350   //  I/O routines:                                    //
00351   //                                                   //
00352   ///////////////////////////////////////////////////////
00353 
00354   //  void printOn( ostream& ostr ) const;
00355 
00356   //  void printDecomposition( ostream& ostr, 
00357   //    const VectorOf<Word>& deco ) const;
00358 
00359   //  HNNExtOfORGroup* readFrom( istream& istr, Chars& errMesg ) const;
00360 
00361   //  void debugPrint( ostream& ostr ) const;
00362 
00363   ///////////////////////////////////////////////////////
00364   //                                                   //
00365   //  IPC tools:                                       //
00366   //                                                   //
00367   ///////////////////////////////////////////////////////
00368 
00369   //  void write( ostream& ostr ) const;
00370   //  void read( istream& istr );
00371 
00372 private:
00373 
00374   ///////////////////////////////////////////////////////
00375   //                                                   //
00376   //  Private helper stuff:                            //
00377   //                                                   //
00378   ///////////////////////////////////////////////////////
00379 
00380   //  int powerOfStableGen(int component, const VectorOf<Word>& deco ) const;
00381   //  bool suspectPinch(int component, const VectorOf<Word>& deco ) const;
00382   //  bool abelianizationTest( const Pinch& pinch, 
00383   //                           const VectorOf<int>& powersOfGens,
00384   //                           const VectorOf<bool>& subgroupGens ) const;
00385   //  Pinch formPinch(int component, const VectorOf<Word>& deco) const;
00386   //  Generator stableLetter( ) const;
00387 
00388 protected:
00389 
00390   Trichotomy conjugacyProblem_cyclicallyReduced( const VectorOf<Word>& uDeco, 
00391     const VectorOf<Word>& vDeco, Word& conjugator ) const;
00392 
00393   class MaximalRootProblem
00394   {
00395   public:
00396     MaximalRootProblem( const Word& w );
00397 
00398     void solve( const HNNExtOfORGroupWithTorsion& group );
00399 
00400     Word root( ) const { return theRoot; }
00401 
00402     int power( ) const { return thePower; }
00403 
00404     Trichotomy answer( ) const { return theAnswer; }
00405 
00406   private:
00407 
00408     bool lexCheckOfStableLetters( const VectorOf<Word>& wDeco, 
00409                                   const int rootLen ) const;
00410 
00411     void lengthN( const HNNExtOfORGroupWithTorsion& H, 
00412                   const VectorOf<Word>& wDeco );
00413 
00414     void setAnswer( const Word& maxRoot, const int maxPower );
00415 
00416     void adjustRoot( );
00417 
00418     // data members:
00419     const Word theWord;
00420     Trichotomy theAnswer;
00421     Word theRoot;
00422     int thePower;
00423     bool isSolved;
00424   };
00425 
00426   ///////////////////////////////////////////////////////
00427   //                                                   //
00428   //  Debugging stuff                                  //
00429   //                                                   //
00430   ///////////////////////////////////////////////////////
00431 
00432 private:
00433 
00434   // Data members:
00435 };
00436 
00437 
00438 
00439 //
00440 //  Helper class:: DoubleCoset
00441 //
00442 
00443 class HNNDoubleCoset
00444 {
00445 public:
00446   HNNDoubleCoset( const SubgroupOfORGroupWithTorsion& Sa,
00447                   const SubgroupOfORGroupWithTorsion& Sbw );
00448 
00449   Trichotomy solve( const Word& f, Word& a, const Word& g, Word& b ) const;
00450 
00451 private:
00452 
00453   Trichotomy oneRelatorWithTorsionSolution( 
00454     const Word& f, Word& a, const Word& g, Word& b ) const;
00455 
00456   Word minimalSpecialForm( const Word& w, 
00457                            const SubgroupOfORGroupWithTorsion S ) const;
00458 
00459   // data members:
00460 
00461   SubgroupOfORGroupWithTorsion A;
00462   SubgroupOfORGroupWithTorsion B;
00463 
00464 };
00465 
00466 
00467 #endif

Generated at Tue Jun 19 09:49:34 2001 for Magnus Classes by doxygen1.2.6 written by Dimitri van Heesch, © 1997-2001