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

/magnus/back_end/AProducts/include/HNNExtension.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: HNNExtension.h,v 1.3 1997/06/30 20:07:03 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:
00011 //
00012 // Status: in progress
00013 //
00014 // Usage:
00015 //
00016 //
00017 // Special Notes:
00018 //
00019 // Revision History:
00020 //
00021 
00022 
00023 #ifndef _HNN_EXTENSION_H_
00024 #define _HNN_EXTENSION_H_
00025 
00026 
00027 #include "FPGroup.h"
00028 
00029 ///////////////////////////////////////////////////////////////////////////
00030 //                                                                       //
00031 //      Class HNNExtensionRep                                            //
00032 //                                                                       //
00033 ///////////////////////////////////////////////////////////////////////////
00034 
00035 class HNNExtensionRep : public FGGroupRep
00036 {
00037 public:
00038 
00039   /////////////////////////////////////////////////////////////////////////
00040   //                                                                     //
00041   //  Constructors:                                                      //
00042   //                                                                     //
00043   /////////////////////////////////////////////////////////////////////////
00044 
00045   HNNExtensionRep( const FPGroup& G );
00046   // Construct an HNN-extension with given presentation G. 
00047   // A stable letter *must* have the largest order in generators of G. 
00048   // No subgroups specified because amalgamated subgroups are determined
00049   // by relators with the stable letter. The rest of the relators of group G 
00050   // defines set of relators of basis group. 
00051 
00052   /////////////////////////////////////////////////////////////////////////
00053   //                                                                     //
00054   // Representation methods:                                             //
00055   //                                                                     //
00056   /////////////////////////////////////////////////////////////////////////
00057   
00058   // Inherited from FGGroupRep:
00059   //   virtual PureRep* clone( ) const;
00060   // No need for clone( ) in derived abstract representation.
00061 
00062   static const Type theHNNExtensionType;
00063 
00064   static Type type( ) { return theHNNExtensionType; }
00065   // Dominates FGGroupRep::type()
00066 
00067   Type actualType( ) const { return type(); }
00068   // Overrides FGGroupRep::actualType();
00069 
00070   /////////////////////////////////////////////////////////////////////////
00071   //                                                                     //
00072   //  Types:                                                             //
00073   //                                                                     //
00074   /////////////////////////////////////////////////////////////////////////
00075 
00076   enum NumberOfSubgroup { A, B };
00077 
00078   enum Pinch { UP, DOWN };
00079 
00080   /////////////////////////////////////////////////////////////////////////
00081   //                                                                     //
00082   //  Accessors:                                                         //
00083   //                                                                     //
00084   /////////////////////////////////////////////////////////////////////////
00085 
00086   const FPGroup& getFPGroup() const { return theFPGroup; }
00087 
00088   virtual const FGGroup& getBasisGroup( ) const = 0;
00089 
00090   Generator stableLetter( ) const { return theNumberOfGenerators; }
00091  
00092   // @dp I don't know how to define accessor to subgroups of the group here.
00093 
00094   /////////////////////////////////////////////////////////////////////////
00095   //                                                                     //
00096   //  Methods and operators which deal with the group:                   //
00097   //                                                                     //
00098   /////////////////////////////////////////////////////////////////////////
00099 
00100   Trichotomy isTrivial( ) const; 
00101   // Override FGGroupRep::isTrivial().
00102 
00103   Trichotomy isFinite( ) const; 
00104   // Override FGGroupRep::isFinite().
00105 
00106   Trichotomy isInfinite( ) const;
00107   // Override FGGroupRep::isInfinite().
00108 
00109   Trichotomy isAbelian( ) const; 
00110   // Override FGGroupRep::isAbelian().
00111 
00112   virtual Trichotomy isFree( ) const = 0; 
00113   // Returns YES if this group is free on its generators, NO if not,
00114   // and DONTKNOW if no answer can be determined.
00115 
00116   /////////////////////////////////////////////////////////////////////////
00117   //                                                                     //
00118   //  Methods and operators which deal with subgroups:                   //
00119   //                                                                     //
00120   /////////////////////////////////////////////////////////////////////////
00121 
00122   bool isSubgroupTrivial( const VectorOf<Word>& vec ) const;
00123   
00124   bool isSubgroupAbelian( const VectorOf<Word>& vec ) const;
00125   
00126   /////////////////////////////////////////////////////////////////////////
00127   //                                                                     //
00128   //  Methods which deal with group elements:                            //
00129   //                                                                     //
00130   /////////////////////////////////////////////////////////////////////////
00131 
00132   Trichotomy areEqual( const Elt& e1, const Elt& e2 ) const {
00133     return wordProblem( e1 * e2.inverse() );
00134   }
00135 
00136   Elt eval( const Word& w ) const { return normalFormOf( w ); }
00137   // Overrides FGGroupRep::eval().
00138 
00139   int lengthOf( const Word& w ) const { return decompositionOf( w ).length() / 2; }
00140   // Counts number of stable letters and its inverses in the given word.
00141 
00142   Word reducedFormOf( const Word& w ) const {
00143     return compose( reducedDecompositionOf( w  ) ); 
00144   }
00145   // Returns a reduced form of the given word.
00146 
00147   Word normalFormOf( const Word& w ) const {
00148     return compose( normalDecompositionOf( w ) );
00149   }
00150   // Returns a normal form of the given word.
00151 
00152   Word cyclicallyReducedFormOf( const Word& w, Word conjugator ) const {
00153     return compose( cyclicallyReducedDecompositionOf( w, conjugator ) );
00154   }
00155   // Returns a cyclially reduced form of the given word.
00156 
00157 
00158   VectorOf<Word> decompositionOf( const Word& w ) const;
00159   VectorOf<Word> reducedDecompositionOf( const Word& w ) const;
00160   VectorOf<Word> normalDecompositionOf( const Word& w ) const;
00161   VectorOf<Word> cyclicallyReducedDecompositionOf( const Word& w, 
00162                                                    Word& conjugator ) const;
00163 
00164   static Word compose( const VectorOf<Word>& V );
00165 
00166   Trichotomy wordProblem( const Word& w ) const; 
00167   // overrides FGGroupRep::wordProblem().
00168 
00169   virtual Trichotomy  maximalRoot( const Word& w, Word& maxRoot, int& maxPower ) const = 0;
00170   // Returns `yes' if maxPower > 1, and `no' if maxPower == 1.
00171   // Returns `dontknow' if a result cannot be determined.
00172   
00173 
00174   /////////////////////////////////////////////////////////////////////////
00175   //                                                                     //
00176   // I/O:                                                                //
00177   //                                                                     //
00178   /////////////////////////////////////////////////////////////////////////
00179 
00180   void printOn( ostream& ) const;
00181   
00182   void printDecomposition( ostream& ostr, const VectorOf<Word>& deco ) const {
00183     printVectorOfWords( ostr, deco );
00184   }
00185   
00186   // GroupRep* readFrom( istream& istr, Chars& errMesg ) const;
00187 
00188   /////////////////////////////////////////////////////////////////////////
00189   //                                                                     //
00190   // IPC tools:                                                          //
00191   //                                                                     //
00192   /////////////////////////////////////////////////////////////////////////
00193 
00194   void write( ostream& ostr ) const;
00195   // overrides FGGroupRep::write().
00196   
00197   void read( istream& istr );
00198   // overrides FGGroupRep::read().
00199 
00200 
00201 protected:
00202 
00203   // Data members:
00204 
00205   FPGroup theFPGroup; // the presentation of the group
00206   //Generator theStableLetter; 
00207   //Chars theNameOfStableLetter;
00208   
00209 
00210   /////////////////////////////////////////////////////////////////////////
00211   //                                                                     //
00212   // Protected functions:                                                //
00213   //                                                                     //
00214   /////////////////////////////////////////////////////////////////////////
00215 
00216 
00217   virtual Word mappingFromSubgroup( NumberOfSubgroup S, const Word& w ) const = 0;
00218 
00219   // Due the fact that the implementations of subgroups are different, 
00220   // we hide this through next interfacing members.
00221 
00222   virtual Word getGeneratorOfSubgroup( const NumberOfSubgroup subgrp, int gen ) const = 0;
00223   
00224   virtual int getNumberOfGeneratorsInSubgroup( const NumberOfSubgroup subgrp ) const = 0;
00225 
00226   virtual bool subgroupContains( const NumberOfSubgroup subgrp, const Word& w ) const  = 0;
00227 
00228   // virtual Word rewriteInSubgroupBasis( const NumberOfSubgroup subgrp, const Word& w ) const = 0;
00229 
00230   virtual Word rightRepresentative( const NumberOfSubgroup subgrp, const Word& w ) const = 0;
00231 
00232 private:
00233 
00234   int powerOfStableGen( int component, const VectorOf<Word>& deco ) const;
00235 
00236   bool suspectPinch( int component, const VectorOf<Word>& decomposition ) const;
00237   Pinch formPinch( int component, const VectorOf<Word>& deco ) const;
00238 };
00239 
00240 
00241 
00242 
00243 ///////////////////////////////////////////////////////////////////////////
00244 //                                                                       //
00245 //      Class HNNExtension                                               //
00246 //                                                                       //
00247 ///////////////////////////////////////////////////////////////////////////
00248 
00249 class HNNExtension 
00250   : public DerivedObjectOf<FGGroup,HNNExtensionRep>
00251 {
00252 public:
00253 
00254   /////////////////////////////////////////////////////////////////////////
00255   //                                                                     //
00256   //  Constructors:                                                      //
00257   //                                                                     //
00258   /////////////////////////////////////////////////////////////////////////
00259 
00260   // No default constructor for pseudo-abstract class.
00261   // Copy constructor, operator=, and destructor supplied by compiler.
00262 
00263   /////////////////////////////////////////////////////////////////////////
00264   //                                                                     //
00265   //  Types:                                                             //
00266   //                                                                     //
00267   /////////////////////////////////////////////////////////////////////////
00268 
00269   typedef HNNExtensionRep::NumberOfSubgroup NumberOfSubgroup;
00270 
00271   /////////////////////////////////////////////////////////////////////////
00272   //                                                                     //
00273   //  Accessors:                                                         //
00274   //                                                                     //
00275   /////////////////////////////////////////////////////////////////////////
00276 
00277   const FPGroup& getFPGroup() const { return look()->getFPGroup(); }
00278   // Returns the presentation of the group.
00279 
00280   const FGGroup& getBasisGroup( ) const { return look()->getBasisGroup(); }
00281   // Returns the basis group of the HNN-extension. 
00282 
00283   Generator stableLetter( ) const { return look()->stableLetter(); }
00284   // Returns a stable letter.
00285 
00286   //  Due the fact that the implementations of subgroups are different, 
00287   //  we hide this through next interfacing members.
00288   // Subgroup getSubgroup( NumberOfSubgroup subgrp ) const;
00289   // virtual getGeneratorOfSubgroup( const NumberOfSubgroup subgrp, int gen ) = 0;
00290   // virtual getNumberOfGeneratorsInSubgroup( const NumberOfSubgroup subgrp ) = 0;
00291 
00292   /////////////////////////////////////////////////////////////////////////
00293   //                                                                     //
00294   //  Methods and operators which deal with the group:                   //
00295   //                                                                     //
00296   /////////////////////////////////////////////////////////////////////////
00297   
00298   // Overrides pseudo-virtual functions from FGGroup:
00299   // 
00300   // Trichotomy isTrivial( ) const; // pseudo-virtual
00301   // Trichotomy isFinite( ) const; // pseudo-virtual
00302   // Trichotomy isInfinite( ) const; // pseudo-virtual
00303   // Trichotomy isAbelian( ) const; // pseudo-virtual
00304 
00305   Trichotomy isFree( ) const { return enhance()->isFree(); }
00306   // Returns YES if this group is free on its generators, NO if not,
00307   // and DONTKNOW if no answer can be determined.
00308 
00309   /////////////////////////////////////////////////////////////////////////
00310   //                                                                     //
00311   //  Methods and operators which deal with subgroups:                   //
00312   //                                                                     //
00313   /////////////////////////////////////////////////////////////////////////
00314 
00315   bool isSubgroupTrivial( const VectorOf<Word>& vec ) const {
00316     return look()->isSubgroupTrivial( vec );
00317   }
00318 
00319   bool isSubgroupAbelian( const VectorOf<Word>& vec ) const {
00320     return look()->isSubgroupAbelian( vec );
00321   }
00322 
00323   /////////////////////////////////////////////////////////////////////////
00324   //                                                                     //
00325   //  Methods which deal with group elements:                            //
00326   //                                                                     //
00327   /////////////////////////////////////////////////////////////////////////
00328 
00329   // Trichotomy wordProblem( const Word& w ) const;
00330   // Overrides pseudo-virtual function.
00331 
00332   int lengthOf( const Word& w ) const { return look()->lengthOf( w ); }
00333 
00334   Word reducedFormOf( const Word& w ) const {
00335     return look()->reducedFormOf( w );
00336   }
00337   // Returns a reduced form of the given word.
00338 
00339   Word normalFormOf( const Word& w ) const {
00340     return look()->normalFormOf( w );
00341   }
00342   // Returns a normal form of the given word.
00343 
00344   // Public data members:
00345 
00346   //@dp++ static Word Conjugator;
00347 
00348   Word cyclicallyReducedFormOf( const Word& w, Word conjugator ) const
00349     //@dp++ = HNNExtension::Conjugator) const 
00350   {
00351     return look()->cyclicallyReducedFormOf( w, conjugator );
00352   }
00353   // Returns a cyclially reduced form of the given word.
00354   
00355   VectorOf<Word> decompositionOf( const Word& w ) const {
00356     return look()->decompositionOf( w );
00357   }
00358   
00359   VectorOf<Word> reducedDecompositionOf( const Word& w ) const {
00360     return look()->reducedDecompositionOf( w );
00361   }
00362   
00363   VectorOf<Word> normalDecompositionOf( const Word& w ) const {
00364     return look()->normalDecompositionOf( w );
00365   }
00366   
00367   VectorOf<Word> cyclicallyReducedDecompositionOf( const Word& w, 
00368                                                    Word& conjugator) const {
00369     return look()->cyclicallyReducedDecompositionOf( w, conjugator );
00370   }
00371 
00372   static Word compose( const VectorOf<Word>& V ) ;
00373   
00374   virtual Trichotomy  maximalRoot( const Word& w, Word& maxRoot, int& maxPower ) const {
00375     return look()->maximalRoot( w, maxRoot, maxPower );
00376   }
00377   // Returns `yes' if maxPower > 1, and `no' if maxPower == 1.
00378   // Returns `dontknow' if a result cannot be determined.
00379 
00380   /////////////////////////////////////////////////////////////////////////
00381   //                                                                     //
00382   // I/O:                                                                //
00383   //                                                                     //
00384   /////////////////////////////////////////////////////////////////////////
00385 
00386   void printDecomposition( ostream& ostr, const VectorOf<Word> deco ) const {
00387     look()->printDecomposition( ostr, deco );
00388   }
00389 
00390   /////////////////////////////////////////////////////////////////////////
00391   //                                                                     //
00392   // IPC tools:                                                          //
00393   //                                                                     //
00394   /////////////////////////////////////////////////////////////////////////
00395 
00396   friend ostream& operator < ( ostream& ostr, const HNNExtension& G )
00397   {
00398     G.look()->write(ostr);
00399     return ostr;
00400   }
00401   
00402   friend istream& operator > ( istream& istr, HNNExtension& G )
00403   {
00404     G.change()->read(istr);
00405     return istr;
00406   }
00407 
00408 protected:
00409 
00410   /////////////////////////////////////////////////////////////////////////
00411   //                                                                     //
00412   // Protected functions:                                                //
00413   //                                                                     //
00414   /////////////////////////////////////////////////////////////////////////
00415 
00416   HNNExtension( HNNExtensionRep *newrep ) 
00417     : DerivedObjectOf<FGGroup,HNNExtensionRep> ( newrep ) { }
00418 
00419 private:
00420   
00421   HNNExtension( ); // Hidden, not to be implemented.
00422 
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