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

/magnus/back_end/Group/include/MSCGroup.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: MSCGroup.h,v 1.5 2000/02/09 23:58:12 bormotov Exp $
00003  */
00004 
00005 // Copyright (C) 1994-1995 The New York Group Theory Cooperative
00006 // See magnus/doc/COPYRIGHT for the full notice.
00007 
00008 // Contents: Definition of the MSCGroup class
00009 //           for metric small cancellation groups
00010 //
00011 // Principal Author: Dmitry Bormotov, Dmitry Pechkin
00012 //
00013 // Status: in progress
00014 //
00015 // Usage:
00016 //
00017 // * Any group satisfying a relator overlap of *strictly* less than
00018 //   one-half is admitted as an MSCGroup. But, there is effectively solution
00019 //   of wordProblem and conjugacyProblem for group with C'(1/6)
00020 //   condition only.
00021 //
00022 //
00023 // Special Notes:
00024 //
00025 // Revision History:
00026 //
00027 
00028 #ifndef _MSC_GROUP_H_
00029 #define _MSC_GROUP_H_
00030 
00031 #include "FPGroupRep.h"
00032 #include "FPGroup.h"
00033 #include "SymmetricRelators.h"
00034 #include "ShortenByRelators.h"
00035 #include "PresentationParser.h"
00036 
00037 
00038 //----------------------- MSCGroup ---------------------------//
00039 
00040 
00041 class MSCGroup {
00042 
00043 friend class MSCGConjugacyProblem;
00044 
00045 public:
00046 
00047 
00048   ///////////////////////////////////////////////////////
00049   //                                                   //
00050   //  Constructors:                                    //
00051   //                                                   //
00052   ///////////////////////////////////////////////////////
00053 
00054   MSCGroup( int ngens = 0 ) : numberOfGenerators ( ngens )
00055   {
00056     SetOf<Word> rels;
00057     makeMSCGroup(ngens, rels);
00058   }
00059   // To construct a group of given number of unnamed generators and
00060   // no relators. Default constructor gives trivial group.
00061 
00062   MSCGroup( int ngens, const SetOf<Word>& rels, int lambda = -1 )
00063   {
00064     makeMSCGroup(ngens, rels, lambda);
00065   }
00066   // To construct a MSC group of given number of unnamed generators and
00067   // given relators. When constructing an MSC group lambda value maybe known.
00068 
00069   MSCGroup( FPGroup G, int lambda = -1 ) 
00070   {
00071     makeMSCGroup(G.numberOfGenerators(), G.getRelators(), lambda);
00072   }
00073   // To construct a metric small cancellation group of given FPGroup.
00074   // When constructing an MSC group lambda value maybe known.
00075 
00076 
00077   ~MSCGroup( ) {
00078     delete symmetricRelators;
00079     delete shortenByRels;
00080   }
00081  
00082 
00083   ///////////////////////////////////////////////////////
00084   //                                                   //
00085   //  Methods and operators which deal with the group  //
00086   //                                                   //
00087   ///////////////////////////////////////////////////////
00088 
00089   int order() const;
00090   // Returns -1(dontknow) iff the group is not C'(1/6).
00091 
00092   Trichotomy isTrivial() const;
00093   // Returns dontknow iff the group is not C'(1/6).
00094 
00095   Trichotomy isFinite() const;
00096   // Returns dontknow iff the group is not C'(1/6).
00097 
00098   Trichotomy isInfinite() const;
00099   // Returns dontknow iff the group is not C'(1/6).
00100 
00101   Trichotomy isAbelian() const;
00102   // Returns dontknow iff the group is not C'(1/6).
00103 
00104   Trichotomy isFree() const;
00105   // Provisional not complete implementation,
00106   // useful only for some particular cases.
00107 
00108   int getMSCLambda() const {
00109     return mscLambda;
00110   } 
00111 
00112 
00113   ///////////////////////////////////////////////////////
00114   //                                                   //
00115   //  Methods which deal with group elements           //
00116   //                                                   //
00117   ///////////////////////////////////////////////////////
00118 
00119   Word shortenByRelators(const Word& w) const;
00120 
00121   Word cyclicallyShortenByRelators(const Word& w) const;
00122   // This method shortens its argument w by relators of the group.
00123   // The word w is interpreted as the cyclic word.
00124   // If word argument w contains a piece of some relator of group, and the
00125   // rest of relator is smaller than this piece, procedure shortens w.
00126 
00127   Elt eval( const Word& w ) const;
00128 
00129   Trichotomy wordProblem( const Word& w ) const;
00130 
00131   Trichotomy areEqual(const Word& w1, const Word& w2) const {
00132     return wordProblem( w1 * w2.inverse() );
00133   }
00134 
00135 
00136 private:
00137 
00138 
00139   ///////////////////////////////////////////////////////
00140   //                                                   //
00141   //  Private functions:                               //
00142   //                                                   //
00143   ///////////////////////////////////////////////////////
00144 
00145   MSCGroup( const MSCGroup& );
00146   // It is hidden, not implemented.
00147 
00148   MSCGroup& operator = ( const MSCGroup& );
00149   // It is hidden, not implemented.
00150 
00151   void calculateLambda( );
00152 
00153   void makeMSCGroup( int ngens, const SetOf<Word>& rels, int lambda = -1 );
00154 
00155   int numOfGens() const {
00156     return numberOfGenerators;
00157   }
00158   
00159   SetOf<Word> getRelators() const {
00160     const VectorOf<Word> v = symmetricRelators->getRelators();
00161     SetOf<Word> S;
00162     int vLen = v.length();
00163     for ( int i = 0; i < vLen; i++ )
00164       S |= v[i];
00165     return S;
00166   }
00167 
00168   Word cyclicallyShortenByRelators( const Word& w, Word& conjugator) const;
00169 
00170 
00171   ///////////////////////////////////////////////////////
00172   //                                                   //
00173   //  Data members:                                    //
00174   //                                                   //
00175   ///////////////////////////////////////////////////////
00176 
00177   SymmetricRelators *symmetricRelators;
00178   // Storage of minimized forms of relators. More compact that relators 
00179   // given by a caller.
00180   // To get full symmetric set of relators the symmetric set iterator 
00181   // is provided.
00182   
00183   ShortenByRelators *shortenByRels;
00184 
00185   int mscLambda;
00186   int numberOfGenerators;
00187 
00188   ///////////////////////////////////////////////////////
00189   //                                                   //
00190   //  Debugging stuff                                  //
00191   //                                                   //
00192   ///////////////////////////////////////////////////////
00193 
00194 #ifdef DEBUG
00195   friend int main(...);
00196 #endif
00197 
00198 };
00199 
00200 #endif

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