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

/magnus/back_end/AProducts/include/HNNExtOfFreeGroup.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: HNNExtOfFreeGroup.h,v 1.2 1997/06/30 20:07:02 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: 
00009 //
00010 // Principal Author: Dmitry Pechkin
00011 //
00012 // Status: in progress
00013 //
00014 // Usage:
00015 //
00016 //
00017 // Special Notes:
00018 //
00019 // Revision History:
00020 //
00021 
00022 
00023 #ifndef _HNN_EXTENSION_OF_FREE_GROUP_H_
00024 #define _HNN_EXTENSION_OF_FREE_GROUP_H_
00025 
00026 
00027 #include "HNNExtension.h"
00028 #include "FreeGroup.h"
00029 #include "SGofFreeGroup.h"
00030 #include "VectorPtr.h"
00031 #include "Automorphism.h"
00032 #include "AP-fixups.h"
00033 
00034 ///////////////////////////////////////////////////////////////////////////
00035 //                                                                       //
00036 //      Class HNNExtOfFreeGroupRep                                       //
00037 //                                                                       //
00038 ///////////////////////////////////////////////////////////////////////////
00039 
00040 class HNNExtOfFreeGroupRep: public HNNExtensionRep 
00041 {
00042 public:
00043 
00044   /////////////////////////////////////////////////////////////////////////
00045   //                                                                     //
00046   //  Constructors:                                                      //
00047   //                                                                     //
00048   /////////////////////////////////////////////////////////////////////////
00049 
00050   HNNExtOfFreeGroupRep( const FreeGroup& F, const Chars& nameOfStableLetter,
00051                         const SGofFreeGroup& subgroupA,
00052                         const SGofFreeGroup& subgroupB );
00053 
00054   /////////////////////////////////////////////////////////////////////////
00055   //                                                                     //
00056   // Representation methods:                                             //
00057   //                                                                     //
00058   /////////////////////////////////////////////////////////////////////////
00059   
00060   PureRep* clone( ) const { return new HNNExtOfFreeGroupRep(*this); }
00061   // overrides HNNExtensionRep::clone()
00062 
00063   static const Type theHNNExtOfFreeGroupType;
00064 
00065   static Type type( ) { return theHNNExtOfFreeGroupType; }
00066   // dominates HNNExtensionRep::type()
00067 
00068   Type actualType( ) const { return type(); }
00069   // overrides HNNExtensionRep::actualType();
00070 
00071   /////////////////////////////////////////////////////////////////////////
00072   //                                                                     //
00073   //  Accessors:                                                         //
00074   //                                                                     //
00075   /////////////////////////////////////////////////////////////////////////
00076 
00077   const FGGroup& getBasisGroup( ) const { 
00078     return theBasisFreeGroup; 
00079   }
00080  
00081   // @dp I don't know how to define accessor to subgroups of the group.
00082 
00083   /////////////////////////////////////////////////////////////////////////
00084   //                                                                     //
00085   //  Methods and operators which deal with the group:                   //
00086   //                                                                     //
00087   /////////////////////////////////////////////////////////////////////////
00088 
00089   virtual int order( ) const { return -1; }
00090   // overrides FGGroupRep::order()
00091 
00092   //Trichotomy isTrivial( ) const { } // pseudo-virtual
00093   //Trichotomy isFinite( ) const { } // pseudo-virtual
00094   //Trichotomy isInfinite( ) const { } // pseudo-virtual
00095   //Trichotomy isAbelian( ) const { } // pseudo-virtual
00096   
00097   Trichotomy isFree( ) const;
00098   // *** Time consuming algorithm ! ***
00099 
00100    /////////////////////////////////////////////////////////////////////////
00101   //                                                                     //
00102   //  Methods and operators which deal with subgroups:                   //
00103   //                                                                     //
00104   /////////////////////////////////////////////////////////////////////////
00105 
00106 
00107   /////////////////////////////////////////////////////////////////////////
00108   //                                                                     //
00109   //  Methods which deal with group elements:                            //
00110   //                                                                     //
00111   /////////////////////////////////////////////////////////////////////////
00112 
00113   // Overrides pseudo-virtual wordProblem(const Elt).
00114 
00115   Trichotomy isProperPower( const Word& w ) const;
00116   // It can always determine a result for cyclic subgroups case only.
00117   // General case is partially supported, it can return `dontknow'.
00118 
00119   Trichotomy maximalRoot( const Word& w, Word& maxRoot, int& maxPower ) const;
00120   // Returns `yes' if maxPower > 1, and `no' if maxPower == 1.
00121   // Returns `dontknow' if a result cannot be determined.
00122   // It can always determine a result for cyclic subgroups case only.
00123   // General case is partially supported, it can return `dontknow'.
00124   
00125   Trichotomy conjugacyProblem( const Word& w, const Word& u ) const {
00126     Word conjugator;
00127     return conjugacyProblem( w, u, conjugator );
00128   }
00129   // Overrides FGGroupRep::conjugacyProblem().
00130 
00131 
00132   Trichotomy conjugacyProblem( const Word& w, const Word& u, Word& conjugator ) const;
00133   // @dp Not implemented yet.
00134 
00135   bool isProperPowerOfSecond( const Word& w, const Word& u, int& k ) const;
00136   // Returns `true' iff it exists a number k>1 such that w^k = u,
00137   // `false' otherwise.
00138 
00139   /////////////////////////////////////////////////////////////////////////
00140   //                                                                     //
00141   // I/O:                                                                //
00142   //                                                                     //
00143   /////////////////////////////////////////////////////////////////////////
00144 
00145   GroupRep* readFrom( istream& istr, Chars& errMesg ) const;
00146   // Overrides FGGroupRep::readFrom().
00147 
00148   /////////////////////////////////////////////////////////////////////////
00149   //                                                                     //
00150   // IPC tools:                                                          //
00151   //                                                                     //
00152   /////////////////////////////////////////////////////////////////////////
00153 
00154   void write( ostream& ostr ) const;
00155   // Overrides HNNExtensionRep::write().
00156   
00157   void read( istream& istr );
00158   // Overrides HNNExtensionRep::read().
00159 
00160 protected:
00161 
00162   /////////////////////////////////////////////////////////////////////////
00163   //                                                                     //
00164   // Protected functions:                                                //
00165   //                                                                     //
00166   /////////////////////////////////////////////////////////////////////////
00167 
00168   void makeSubgroupsMappings();
00169 
00170   void makeReducedCyclicPresentation( ) const;
00171 
00172   Word mappingFromSubgroup( const NumberOfSubgroup S, const Word& w ) const;
00173 
00174   Trichotomy conjugacyProblem_reduced( const Word& u, const Word& v, 
00175                                        Word& conjugator ) const;
00176 
00177   Trichotomy conjugateInSubgroups( NumberOfSubgroup S, const Word& u, 
00178                                    const Word& v, Word& conjugator, 
00179                                    bool oneIteration ) const;
00180   // It determines whether the word `u' is conjugated (in HNN-extention) 
00181   // with an element of the given amalgamated subgroup `S' and last one 
00182   // is conjugated (in free group) with the word `v'.
00183 
00184   Trichotomy conjugacyProblem_case1( const Word& u, const Word& v, 
00185                                      Word& conjugator ) const;
00186   // Conjugacy problem for special case: amalgamated words are cyclically
00187   // reduced, and every of u, v belongs to the basis group.
00188 
00189   Trichotomy conjugacyProblem_case2(VectorOf<Word>& uDec, VectorOf<Word>& vDec, 
00190                                     Word& conjugator ) const;
00191 
00192   // Due the fact that the implementations of subgroups are different, 
00193   // we hide this through next interfacing members.
00194 
00195   Word getGeneratorOfSubgroup( const NumberOfSubgroup S, const int gen ) const {
00196     return  theSubgroups[S].generators()[gen];
00197   }
00198 
00199   int getNumberOfGeneratorsInSubgroup( const NumberOfSubgroup S ) const {
00200     return  theSubgroups[S].generators().length();
00201   }
00202 
00203   bool subgroupContains( const NumberOfSubgroup S, const Word& w ) const {
00204     return  theSubgroups[S].contains( w );
00205   }
00206 
00207   //Word rewriteInSubgroupBasis( const NumberOfSubgroup S, const Word& w ) const;
00208 
00209   Word rightRepresentative( const NumberOfSubgroup S, const Word& w ) const {
00210     return theSubgroups[S].rightSchreierRepresentative( w );
00211   }
00212 
00213 
00214   ///////////////////////////////////////////
00215   //                                       //
00216   // Helper class SpecialHNNExtOfFreeGroup //
00217   //                                       //
00218   ///////////////////////////////////////////
00219 
00220   // This class contains a cyclically reduced presentation of an HNN-extension
00221   // of a free group with some helper info.
00222 
00223   struct SpecialHNNExtOfFreeGroup {
00224   public:
00225 
00226     SpecialHNNExtOfFreeGroup() 
00227       : H(0), toOriginalPresentation( FreeGroup(0), VectorOf<Word>(0) ) { }
00228     // dumb ctor.
00229 
00230     SpecialHNNExtOfFreeGroup( const Automorphism& mapToOriginalPresentation,
00231                               const FreeGroup& basisFreeGroup,
00232                               const Chars& nameOfStableLetter,
00233                               const SGofFreeGroup& A,
00234                               const SGofFreeGroup& B,
00235                               bool  areAmalgSubgroupsConjugateSeparated,
00236                               const VectorOf<Word>& rootsOfSubgroupsGens,
00237                               const VectorOf<int>&  powersOfSubgroupsGens
00238                               );
00239 
00240     SpecialHNNExtOfFreeGroup( const SpecialHNNExtOfFreeGroup& S );
00241     ~SpecialHNNExtOfFreeGroup() { delete H; }
00242     SpecialHNNExtOfFreeGroup& operator = ( const SpecialHNNExtOfFreeGroup& S );
00243 
00244     bool doneInit( ) const { return H != 0; }
00245 
00246     const HNNExtOfFreeGroupRep& presentation() const;
00247 
00248     Automorphism         toOriginalPresentation;
00249     bool                 areAmalgSubgroupsConjugateSeparated;
00250     VectorOf<Word>       theRootsOfSubgroupsGens;
00251     VectorOf<int>        thePowersOfSubgroupsGens;   
00252 
00253   private:
00254     HNNExtOfFreeGroupRep *H;
00255   };
00256     
00257 
00258   //////////////////////////////////////
00259   //                                  //
00260   // Utility class MaximalRootProblem //
00261   //                                  //
00262   //////////////////////////////////////
00263 
00264   class MaximalRootProblem {
00265   public:
00266     MaximalRootProblem( const Word& w );
00267     
00268     // status query:
00269 
00270     Trichotomy answer() const { return theAnswer; }
00271     Word root() const { return theRoot; }
00272     int power() const { return thePower; }
00273     void solve( const SpecialHNNExtOfFreeGroup& group );
00274 
00275   private:
00276 
00277     void length0( const Word& w );
00278     void lengthN( const VectorOf<Word> wDeco );
00279     void setAnswer( const Word& root, int power );
00280 
00281     SpecialHNNExtOfFreeGroup theGroup;
00282     Word theWord;
00283     Word theRoot;
00284     int  thePower;
00285     Trichotomy theAnswer;
00286     bool isSolved;
00287     Word stableLetter;
00288   };
00289   
00290   friend class MaximalRootProblem;
00291 
00292   // Data members:
00293 
00294   FreeGroup theBasisFreeGroup;
00295   VectorPtrOf<SGofFreeGroup> theSubgroups; // vector of length 2.
00296   VectorOf< VectorOf<Word> > mapNielsenGensToSubgroupGens;//[2];
00297   
00298   // This member contains useful information for solving conjugacy
00299   // and maximal root problems.
00300   SpecialHNNExtOfFreeGroup reducedPresentation;
00301 };
00302 
00303 
00304 
00305 
00306 ///////////////////////////////////////////////////////////////////////////
00307 //                                                                       //
00308 //      Class HNNExtOfFreeGroup                                          //
00309 //                                                                       //
00310 ///////////////////////////////////////////////////////////////////////////
00311 
00312 class HNNExtOfFreeGroup  
00313   : public DerivedObjectOf< HNNExtension, HNNExtOfFreeGroupRep>
00314 {
00315 public:
00316 
00317   /////////////////////////////////////////////////////////////////////////
00318   //                                                                     //
00319   //  Constructors:                                                      //
00320   //                                                                     //
00321   /////////////////////////////////////////////////////////////////////////
00322 
00323   HNNExtOfFreeGroup( const FreeGroup& F, 
00324                      const Chars& nameOfStableLetter,
00325                      const SGofFreeGroup& subgroupA,
00326                      const SGofFreeGroup& subgroupB )
00327   : DerivedObjectOf< HNNExtension, HNNExtOfFreeGroupRep>(
00328     new HNNExtOfFreeGroupRep(F, nameOfStableLetter, subgroupA, subgroupB )
00329         ) { }
00330 
00331   /////////////////////////////////////////////////////////////////////////
00332   //                                                                     //
00333   //  Accessors:                                                         //
00334   //                                                                     //
00335   /////////////////////////////////////////////////////////////////////////
00336 
00337   // inherited  FPGroup getFPGroup() const { return look()->getFPGroup(); }
00338 
00339   // const FGGroup& getBasisGroup( ) const;
00340   // Overrides pseudo-virtual `HNNExtension::getBasisGroup()'.
00341 
00342   /////////////////////////////////////////////////////////////////////////
00343   //                                                                     //
00344   //  Methods and operators which deal with the group:                   //
00345   //                                                                     //
00346   /////////////////////////////////////////////////////////////////////////
00347   
00348   // Overrides pseudo-virtual functions from FGGroup:
00349   // 
00350   // int order( ) const; // pseudo-virtual
00351   // 
00352   // Trichotomy isFree( ) const { } // pseudo-virtual
00353   // *** Time consuming algorithm ! ***
00354 
00355   /////////////////////////////////////////////////////////////////////////
00356   //                                                                     //
00357   //  Methods and operators which deal with subgroups:                   //
00358   //                                                                     //
00359   /////////////////////////////////////////////////////////////////////////
00360 
00361 
00362   /////////////////////////////////////////////////////////////////////////
00363   //                                                                     //
00364   //  Methods which deal with group elements:                            //
00365   //                                                                     //
00366   /////////////////////////////////////////////////////////////////////////
00367 
00368   Trichotomy isProperPower( const Word& w ) const {
00369     return look()->isProperPower( w );
00370   }
00371   // It can always determine a result for cyclic subgroups case only.
00372   // General case is partially supported, it can return `dontknow'.
00373 
00374   // Trichotomy maximalRoot( const Word& w, Word& maxRoot, int& maxPower ) const;
00375   // overrides pseudo-virtual HNNExtension::maximalRoot().
00376   // It can determines a result for cyclic subgroups case only.
00377   // General case is partially supported, it can returns `dontknow'.
00378 
00379   Trichotomy conjugacyProblem( const Word& w, const Word& u, Word& conjugator ) const {
00380     return look()->conjugacyProblem( w, u, conjugator );
00381   }
00382 
00383   bool isProperPowerOfSecond( const Word& w, const Word& u, int& k ) const {
00384     return look()->isProperPowerOfSecond( w, u, k ); 
00385   }
00386   // Returns `true' iff it exists a number k>1 such that w^k = u,
00387   // `false' otherwise.
00388 
00389   /////////////////////////////////////////////////////////////////////////
00390   //                                                                     //
00391   // I/O:                                                                //
00392   //                                                                     //
00393   /////////////////////////////////////////////////////////////////////////
00394 
00395   /////////////////////////////////////////////////////////////////////////
00396   //                                                                     //
00397   // IPC tools:                                                          //
00398   //                                                                     //
00399   /////////////////////////////////////////////////////////////////////////
00400 
00401   friend ostream& operator < ( ostream& ostr, const HNNExtOfFreeGroup& G )
00402   {
00403     G.look()->write(ostr);
00404     return ostr;
00405   }
00406   
00407   friend istream& operator > ( istream& istr, HNNExtOfFreeGroup& G )
00408   {
00409     G.change()->read(istr);
00410     return istr;
00411   }
00412 
00413 protected:
00414 
00415   /////////////////////////////////////////////////////////////////////////
00416   //                                                                     //
00417   // Protected functions:                                                //
00418   //                                                                     //
00419   /////////////////////////////////////////////////////////////////////////
00420 
00421   HNNExtOfFreeGroup( HNNExtOfFreeGroupRep *newrep ) 
00422     : DerivedObjectOf<HNNExtension, HNNExtOfFreeGroupRep> ( newrep ) { }
00423 };
00424 
00425 #endif

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