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

/magnus/back_end/Subgroup/include/SGofFreeGroup.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: SGofFreeGroup.h,v 1.7 2000/09/29 20:18:04 bormotov Exp $
00003  */
00004 
00005 // Copyright (C) 1994 The New York Group Theory Cooperative
00006 // See magnus/doc/COPYRIGHT for the full notice.
00007 
00008 // Contents: Definition of SGofFreeGroup and SGofFreeGroupRep classes.
00009 //
00010 // Principal Authors: Sergei Lyutikov, Roger Needham
00011 //
00012 // Status: Draft
00013 //
00014 // Description:
00015 //
00016 //   A subgroup stores a shared-reference `copy' of its parent group.
00017 //   Enhancements to the parent group are thus available to its
00018 //   subgroups. The subgroup is generated by (formal) words interpretable
00019 //   in the generators of the parent group.
00020 //
00021 // Special Notes:
00022 //
00023 //   Since SubgroupGraph works ONLY with freely reduced word all words
00024 //   should be freely reduced here before passing them to methods of
00025 //   SubgroupGraph.
00026 //
00027 // Revision History:
00028 //
00029 // * First implemented: april 12, 1995
00030 //
00031 // * 5/8/95 rn added members:
00032 //     SGofFreeGroup SGofFreeGroup::MHallCompletion( )
00033 //     SGofFreeGroupRep* SGofFreeGroupRep::MHallCompletion( )
00034 //     SGofFreeGroupRep::SGofFreeGroupRep( const FreeGroup& parent,
00035 //                                         SubgroupGraph SGG )
00036 //
00037 // * 10/16/96 @dp added members:
00038 //     bool SGofFreeGroup::isMalnormal( Word& conjugator )
00039 //     bool SGofFreeGroupRep::isMalnormal( Word& conjugator )
00040 //
00041 // * 03/03/97 @dp added:
00042 //     void SGofFreeGroup::printWord( ostream& ostr, const Word& w ) const;
00043 //
00044 
00045 #ifndef _SGOFFREEGROUP_H_
00046 #define _SGOFFREEGROUP_H_
00047 
00048 #include "ObjectOf.h"
00049 #include "RefCounter.h"
00050 #include "FreeGroup.h"
00051 #include "SubgroupGraph.h"
00052 
00053 class SGofFreeGroupRep : public GenericRep {
00054 
00055 public:
00056 
00057   // Constructors:
00058 
00059   // Copy constructor supplied by compiler
00060 
00061   SGofFreeGroupRep( const FreeGroup& parent, const VectorOf<Word>& gens );
00062 
00063   SGofFreeGroupRep( const FreeGroup& parent, SubgroupGraph SGG ) :
00064     computedNielsenBasis(false),
00065     theSubgroupGraph(SGG),
00066     builtSubgroupGraph(true),
00067     theGenerators(SGG.nielsenBasis()),
00068     theParentGroup(parent)
00069   { }
00070 
00071 
00072   // Representation methods:
00073 
00074   PureRep* clone( ) const { return new SGofFreeGroupRep(*this); }
00075 
00076   static const Type theSGofFreeGroupType;
00077 
00078   static Type type( ) { return theSGofFreeGroupType; }
00079 
00080   virtual Type actualType( ) const { return type(); }
00081 
00082   int hash() const;
00083 
00084   // Operators:
00085 
00086   // Methods dealing with group structure:
00087  
00088   int order( ) { return rank() == 0; }
00089   Bool isTrivial( ) { return rank() == 0; }
00090   Bool isFinite( ) { return rank() == 0; }
00091   Bool isInfinite( ) { return !isFinite(); }
00092   Bool isAbelian( ) { return rank() < 2; } 
00093   bool isMalnormal( Word& conjugator );
00094 
00095   SGofFreeGroupRep* join(SGofFreeGroupRep& SGR);
00096   // Returns the join of this subgroup and the argument.
00097 
00098   SGofFreeGroupRep* intersection(SGofFreeGroupRep& SGR);
00099   // Returns the intersection of this subgroup and the argument.
00100 
00101   Bool isNormal( );
00102 
00103   VectorOf<Word> normalizer( );
00104 
00105   VectorOf<Word> nielsenBasis( );
00106   // Returns a Nielsen basis for the subgroup.
00107 
00108   Word nielsenWord(int i);
00109   // Returns an  i^th element of the Nielsen basis.
00110 
00111   Word inNielsenWords(const Word& w);
00112   // Returns the word `w' written in elements of the Nielsen basis.
00113 
00114   int rank();
00115   // Returns the rank of this subgroup as a free group.
00116 
00117   // Methods dealing with group elements:
00118 
00119   // Trichotomy areEqual(const Elt&, const Elt&) const { return DONTKNOW; }
00120   //@rn can do
00121 
00122   // Elt multiply(const Elt&, const Elt&) const
00123   // result is as actual type of args: if formal words in subgroup
00124   // generators, then such; if elt in parent group, then such
00125   // if mixed, then nonsense
00126 
00127   // Elt inverseOf(const Elt&) const
00128   // @rn?
00129          
00130   // Elt raiseToPower(const Elt&, int) const
00131   // @rn?
00132 
00133   // Elt conjugateBy(const Elt&, const Elt&) const
00134 
00135   // Elt commutator(const Elt&, const Elt&) const
00136   // @rn?
00137 
00138   Elt eval( const Word& w ) const;
00139   // `w' is in the subgroup's generators. Returns the word `w' written
00140   // in the free group's generators.
00141 
00142   Bool wordProblem( const Word& w ) const;
00143   // `w' is a word in the subgroup's generators. Returns TRUE iff
00144   // `w' is trivial in the free group.
00145   
00146   Bool conjugacyProblem( const Word& u, const Word& v ) const;
00147   // `u' and `v' are words in the subgroup's generators. Returns TRUE
00148   // iff `u' and `v' are conjugate in the free group.
00149 
00150   Bool contains(const Word& w);
00151   // Returns TRUE iff this subgroup contains `w'.
00152 
00153   Bool contains(const SetOf<Word>& S);
00154   // Returns TRUE iff this subgroup contains the subgroup generated by `S'.
00155 
00156   Bool contains(const VectorOf<Word>& V);
00157   // Returns TRUE iff this subgroup contains the subgroup generated by `V'.
00158 
00159   Bool contains(const SGofFreeGroupRep& SGR);
00160   // Returns TRUE iff this subgroup contains `SG'.
00161 
00162   Bool equalTo(const SetOf<Word>& S);
00163   // Returns TRUE iff this subgroup and the subgroup generated by `S' are equal.
00164 
00165   Bool conjugateInSubgroup(const Word& w, Word& conjugator);
00166   // Returns TRUE iff some conjugate of `w' is in the subgroup.
00167   // If TRUE, `conjugator' is set to the conjugator.
00168 
00169   Bool conjugateInSubgroup(const SetOf<Word>& S, Word& conjugator);
00170   // Returns TRUE iff some conjugate of the subgroup generated by `S' is
00171   // in the subgroup. If TRUE, `conjugator' is set to the conjugator.
00172 
00173   bool conjugateTo(const SetOf<Word>& S);
00174   // Returns true iff this subgroup and the argument are conjugate.
00175 
00176   long powerInSubgroup( const Word& w );
00177   // returns `the minimal power' or 0 if there are no powers of the
00178   // element `aWord' in H.
00179 
00180   int findIndex();
00181   // Returns the index of the subgroup or 0 if infinite.
00182 
00183   VectorOf<Word> findWhiteheadBasis();
00184   // Finds the subgroup of the free group authomorphic to this with
00185   // smallest sum of lengths of generators.
00186   // Returns a vector of generators.
00187 
00188   Bool isAFreeFactor();
00189   // Returns TRUE iff this subgroup is a free factor.
00190 
00191   Bool generatesTheFreeGroup();
00192 
00193   Word rightSchreierRepresentative(const Word& w);
00194 
00195   SGofFreeGroupRep* MHallCompletion( );
00196 
00197   void makeSubgroupGraph( );
00198 
00199   // I/O:
00200  
00201   void printOn(ostream&) const;
00202 
00203   SGofFreeGroupRep* readFrom(istream&, Chars&) const { return 0; }
00204 
00205   void printGenerator( ostream& ostr, int n ) const;
00206   void printGenerators( ostream& ostr ) const;
00207   void printWord( ostream& ostr, const Word& w ) const;
00208   // w is a word in the subgroup's generators.
00209   
00210 
00211   // Data members:
00212 
00213   //@rn Provisional flags:
00214   bool computedNielsenBasis;
00215   bool builtSubgroupGraph;
00216 
00217   VectorOf<Word> theGenerators;
00218   VectorOf<Word> NielsenBasis;
00219 
00220   SubgroupGraph theSubgroupGraph;
00221 
00222   //@rn VectorOf<Chars> theNamesOfGenerators;
00223   //@rn Someday the end user might name generators.
00224 
00225   FreeGroup theParentGroup;
00226 
00227 private:
00228 
00229   SGofFreeGroupRep& operator = ( const SGofFreeGroupRep& );
00230   // disable assignment
00231 
00232 };
00233 
00234 
00235 //------------------------- SGofFreeGroup ---------------------------//
00236 
00237 
00238 class SGofFreeGroup : public GenericObject {
00239 
00240 public:
00241 
00242   ///////////////////////////////////////////////////////
00243   //                                                   //
00244   //  Constructors                                     //
00245   //                                                   //
00246   ///////////////////////////////////////////////////////
00247 
00248   SGofFreeGroup( const FreeGroup& parent, const VectorOf<Word>& gens )
00249   : GenericObject( new SGofFreeGroupRep(parent,gens) )
00250   { }
00251   // to make a finitely generated SGofFreeGroup with a vector of unnamed
00252   // generators
00253 
00254 
00255   ///////////////////////////////////////////////////////
00256   //                                                   //
00257   //  Accessors                                        //
00258   //                                                   //
00259   ///////////////////////////////////////////////////////
00260 
00261   int hash() const { return look()->hash(); }
00262 
00263   bool operator == ( const SGofFreeGroup& g) const;
00264 
00265   const FreeGroup& parentGroup( ) const { return look()->theParentGroup; }
00266 
00267   const VectorOf<Word>& generators( ) const { return look()->theGenerators; }
00268 
00269   static Type type( ) { return SGofFreeGroupRep::type(); }
00270 
00271   Type actualType( ) const { return look()->actualType(); }
00272 
00273   ///////////////////////////////////////////////////////
00274   //                                                   //
00275   //  Group structure methods                          //
00276   //                                                   //
00277   ///////////////////////////////////////////////////////
00278  
00279   int order( ) { return enhance()->order( ); }
00280   Bool isTrivial( ) { return enhance()->isTrivial( ); }
00281   Bool isFinite( ) { return enhance()->isFinite( ); }
00282   Bool isInfinite( ) { return enhance()->isInfinite( ); }
00283   Bool isAbelian( ) { return enhance()->isAbelian( ); }
00284 
00285   bool isMalnormal( Word& conjugator ) { return enhance()->isMalnormal(conjugator); }
00286   // A subgroup is malnormal iff the intersection of the subgroup and
00287   // conjugation of the one by any element from the difference 
00288   // of the parent group and the subgroup is not trivial.
00289   // The function returns `false' and a word to conjugate the 
00290   // if the subgroup is not malnormal. If the subgroup is malnormal
00291   // then it returns only `true' and the parameter `conjugator' is meanless.
00292 
00293   SGofFreeGroup join(SGofFreeGroup& SG) {
00294     return SGofFreeGroup(enhance()->join(*SG.enhance()));
00295   }
00296   // Returns the join of this subgroup and the argument.
00297 
00298   SGofFreeGroup intersection(SGofFreeGroup& SG) {
00299     return SGofFreeGroup(enhance()->intersection(*SG.enhance()));
00300   }
00301   // Returns the intersection of this subgroup and the argument.
00302 
00303   Bool isNormal( ) { return enhance()->isNormal(); }
00304 
00305   VectorOf<Word> normalizer( ) { return enhance()->normalizer(); }
00306 
00307   VectorOf<Word> nielsenBasis( ) { return enhance()->nielsenBasis(); }
00308   // Returns a Nielsen basis for this subgroup.
00309 
00310   Word nielsenWord(int i) { return enhance()->nielsenWord(i); }
00311   // Returns an  i^th element of the Nielsen basis.
00312 
00313   Word inNielsenWords(const Word& w) { return enhance()->inNielsenWords(w); }
00314   // Returns the word `w' written in elements of the Nielsen basis.
00315 
00316   int rank() { return enhance()->rank(); }
00317   // Returns the rank of this subgroup as a free group
00318 
00319   SGofFreeGroup MHallCompletion( ) {
00320          return SGofFreeGroup( enhance()->MHallCompletion() );
00321   }
00322 
00323 
00324   ///////////////////////////////////////////////////////
00325   //                                                   //
00326   //  Methods which deal with subgroup elements        //
00327   //                                                   //
00328   ///////////////////////////////////////////////////////
00329 
00330   // Trichotomy areEqual(const Elt& e1, const Elt& e2) const; 
00331   // Elt firstElt( ) const;                                   
00332   // Elt nextElt(const Elt& e) const;                         
00333   // Elt multiply(const Elt& e1, const Elt& e2) const;        
00334   // Elt inverseOf(const Elt& e) const;                       
00335   // Elt raiseToPower(const Elt& e, int n) const;             
00336   // Elt conjugateBy(const Elt& e1, const Elt& e2) const;     
00337   // Elt commutator(const Elt& e1, const Elt& e2) const;      
00338 
00339   Elt eval( const Word& w ) const { return look()->eval(w); }
00340   // `w' is in the subgroup's generators. Returns the word `w' written
00341   // in the free group's generators.
00342 
00343   Bool wordProblem( const Word& w ) const {
00344     return look()->wordProblem(w);
00345   }
00346   // `w' is a word in the subgroup's generators. Returns TRUE iff
00347   // `w' is trivial in the free group.
00348 
00349   Bool conjugacyProblem( const Word& u, const Word& v ) const {
00350     return look()->conjugacyProblem(u,v);
00351   }
00352 
00353   Bool contains(const Word& w) { return enhance()->contains(w); }
00354   // Returns TRUE iff this subgroup contains `w'.
00355 
00356   Bool contains(const SetOf<Word>& S) { return enhance()->contains(S); }
00357   // Returns TRUE iff this subgroup contains the subgroup generated by `S'.
00358 
00359   Bool contains(const VectorOf<Word>& V) { return enhance()->contains(V); }
00360   // Returns TRUE iff this subgroup contains the subgroup generated by `V'.
00361 
00362   Bool contains(const SGofFreeGroup& SG) { 
00363     return enhance()->contains(*SG.look());
00364   }
00365   // Returns TRUE iff this subgroup contains `SG'.
00366 
00367   Bool equalTo(const SetOf<Word>& S) { return enhance()->equalTo(S); }
00368   // Returns TRUE iff this subgroup and the subgroup generated by `S' are equal.
00369 
00370   Bool conjugateInSubgroup(const Word& w, Word& conjugator) {
00371          return enhance()->conjugateInSubgroup(w,conjugator);
00372   }
00373   // Returns TRUE iff some conjugate of `w' is in the subgroup.
00374   // If TRUE, `conjugator' is set to the conjugator.
00375 
00376   Bool conjugateInSubgroup(const SetOf<Word>& S, Word& conjugator) {
00377          return enhance()->conjugateInSubgroup(S,conjugator);
00378   }
00379   // Returns TRUE iff some conjugate of the subgroup generated by `S' is
00380   // in the subgroup. If TRUE, `conjugator' is set to the conjugator.
00381 
00382   bool conjugateTo(const SetOf<Word>& S) {
00383     return enhance()->conjugateTo(S);
00384   }
00385   // Returns true iff this subgroup and the argument are conjugate.
00386 
00387   long powerInSubgroup( const Word& w ) {
00388          return enhance()->powerInSubgroup(w);
00389   }
00390   // returns `the minimal power' or 0 if there are no powers of the
00391   // element `aWord' in H.
00392 
00393   int findIndex() { return enhance()->findIndex(); }
00394   // Returns the index of the subgroup or 0 if infinite.
00395 
00396   VectorOf<Word> findWhiteheadBasis() {
00397     return enhance()->findWhiteheadBasis();
00398   }
00399   // Finds the subgroup of the free group authomorphic to this with
00400   // smallest sum of lengths of generators.
00401   // Returns a vector of generators.
00402 
00403   Bool isAFreeFactor() { return enhance()->isAFreeFactor(); }
00404   // Returns TRUE iff this subgroup is a free factor.
00405 
00406   Bool generatesTheFreeGroup() {
00407          return enhance()->generatesTheFreeGroup();
00408   }
00409 
00410   Word rightSchreierRepresentative(const Word& w) {
00411          return enhance()->rightSchreierRepresentative(w);
00412   }
00413 
00414   ///////////////////////////////////////////////////////
00415   //                                                   //
00416   //  Methods which deal with sets of group elements   //
00417   //                                                   //
00418   ///////////////////////////////////////////////////////
00419  
00420   // @rn Want these?
00421   // SetOf<Elt> setMultiply(const SetOf<Elt>& S1, const SetOf<Elt>& S2) const;
00422   // SetOf<Elt> setMultiply(const Elt& e, const SetOf<Elt>& S) const;
00423   // SetOf<Elt> setMultiply(const SetOf<Elt>& S, const Elt& e) const;
00424   // SetOf<Elt> conjugateBy(const SetOf<Elt>& S1, const SetOf<Elt>& S2) const;
00425   // SetOf<Elt> conjugateBy(const Elt& e, const SetOf<Elt>& S) const;
00426   // SetOf<Elt> conjugateBy(const SetOf<Elt>& S, const Elt& e) const;
00427   // void closeUnderInverses(SetOf<Elt>& S) const;
00428   // void closeUnderCyclicPermutations(SetOf<Word>& S) const;
00429 
00430   ///////////////////////////////////////////////////////
00431   //                                                   //
00432   //  I/O                                              //
00433   //                                                   //
00434   ///////////////////////////////////////////////////////
00435  
00436   void printWord( ostream& ostr, const Word& w ) const {
00437     look()->printWord( ostr, w );
00438   } 
00439   // w is a word in the subgroup's generators.
00440 
00441  
00442   ///////////////////////////////////////////////////////
00443   //                                                   //
00444   //  Representation access methods                    //
00445   //                                                   //
00446   ///////////////////////////////////////////////////////
00447 
00448 protected:
00449 
00450 
00451   // Shadow representation accessors to get representations of the
00452   // right type in the members of this class:
00453 
00454   const SGofFreeGroupRep* look( ) const {
00455          return (const SGofFreeGroupRep*)GenericObject::look();
00456   }
00457   SGofFreeGroupRep* enhance( ) const {
00458          return (SGofFreeGroupRep*)GenericObject::enhance();
00459   }
00460   SGofFreeGroupRep* change( ) {
00461          return (SGofFreeGroupRep*)GenericObject::change();
00462   }
00463 
00464   // Special wrapping constructor to wrap new representations (returned
00465   // by eg. delegated methods) and for GenericObject initialisation by derived
00466   // classes:
00467 
00468   SGofFreeGroup( SGofFreeGroupRep* newrep ) : GenericObject(newrep) { }
00469 
00470 };
00471 
00472 
00473 
00474 
00475 Word expressWordInSubgroupGenerators( const SGofFreeGroup& H, const Word& w);
00476 // Returns the word `w' written in the given generators of the subgroup `H'.
00477 
00478 #endif

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