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

/magnus/back_end/Group/include/FPGroupRep.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: FPGroupRep.h,v 1.5 2000/03/03 02:44:11 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 the FPGroupRep class.
00009 //           The name is abbreviated to fit in a library.
00010 //
00011 // Principal Authors: Stephane Collart, Roger Needham
00012 //
00013 // Status: in progress
00014 //
00015 // Revision History:
00016 //
00017 // 12/16/94 rn Added provisional data member word_problem, for experimentation.
00018 //          The wordProblem method now consults it. The ctors had to change too.
00019 //
00020 //  5/01/95 rn removed the WordProblem data member.
00021 //
00022 // Discussion:
00023 //
00024 // * The problem of storing flags: many flags signalling properties of
00025 //   groups imply that information was computed in addition to the
00026 //   setting of the flag: for small cancellation, the value of lamda,
00027 //   for free, the rank, etc.
00028 //   Storing both a flag and the value of some information can be
00029 //   redundant, making consistent manipulation more cumbersome.
00030 //   The helper class FPGroupRep::MetricSmallCancellationLambda is a
00031 //   tentative and partial answer to this, by providing both value
00032 //   and setting handles, but keeping only one effective data record.
00033 //   Note that the problem of storing additional information generated
00034 //   in computations, such as eg. more relators, is left open by this.
00035 //
00036 // * Is it really appropriate for a group to accumulate information
00037 //   about itself? There seems to be a danger of redundancy of
00038 //   facilities if eg. an FPGroup both remembers it is a MSCGroup,
00039 //   and behaves as such, and at the same time a full blown MSCGroup
00040 //   class is provided with much the same abilities.
00041 //
00042 // Bugs:
00043 //
00044 // * isTrivialElt(Elt) calls wordProblem(Word), implying the assumption
00045 //   the arg is always an actual word: this seems highly questionable.
00046 //   
00047 // Special Notes:
00048 //
00049 //
00050 
00051 #ifndef _FIN_PRES_GROUP_REP_H_
00052 #define _FIN_PRES_GROUP_REP_H_
00053 
00054 
00055 #include <Integer.h>
00056 #include "FGGroupRep.h"
00057 #include "File.h"
00058 
00059 struct FPGroupRep : FGGroupRep {
00060 
00061   // Methods dealing with the finitely presented group rep:
00062 
00063 // Constructors:
00064 
00065   // Copy constructor and operator= provided by compiler (do deep copy).
00066   
00067   FPGroupRep( int ngens )
00068   : FGGroupRep(ngens),
00069          isMetricSmallCancellation(MetricSmallCancellationLambda::infinity)
00070   { }
00071   // Make a rep with ngens unnamed generators, no relators.
00072 
00073   FPGroupRep( const VectorOf<Chars>& gennames )
00074   : FGGroupRep( gennames ),
00075          isMetricSmallCancellation(MetricSmallCancellationLambda::infinity)
00076   { }
00077   // Make a rep with named generators, no relators.
00078 
00079   FPGroupRep( int ngens, const SetOf<Word>& rels )
00080   : FGGroupRep(ngens),
00081          relators(rels)
00082   { }
00083   // Make a rep with ngens unnamed generators, given relators.
00084   
00085   FPGroupRep( const VectorOf<Chars>& gennames, const SetOf<Word>& rels )
00086   : FGGroupRep( gennames ),
00087     relators(rels)
00088   { }
00089   // Make a rep with named generators, given relators.
00090   
00091   // Destructor provided by compiler.
00092 
00093 // Accessors / Manipulators:
00094 
00095   virtual SetOf<Word>& setRelators( const SetOf<Word>& r ) {
00096         isMetricSmallCancellation.reset();
00097         relators = r;
00098         return relators;
00099         // @stc can be condensed to return relators = r if and when set
00100         // assignment-like operators are made to return refs
00101   }
00102 
00103   virtual SetOf<Word>& addRelators( const SetOf<Word>& r ) {
00104     isMetricSmallCancellation.reset();
00105         relators |= r;
00106     return relators;
00107     // @stc can be condensed to return relators |= r if and when set
00108     // assignment-like operators are made to return refs
00109   }
00110  
00111   virtual SetOf<Word>& removeRelators( const SetOf<Word>& r ) {
00112     isMetricSmallCancellation.reset();
00113     relators -= r;
00114     return relators;
00115     // @stc can be condensed to return relators -= r if and when set
00116     // assignment-like operators are made to return refs
00117   }
00118 
00119 //
00120 // Representation methods:
00121 //
00122   
00123   PureRep* clone( ) const { return new FPGroupRep(*this); }
00124   // overrides FGGroupRep::clone()
00125 
00126   static const Type theFPGroupType;
00127 
00128   static Type type( ) { return theFPGroupType; }
00129   // dominates FGGroupRep::type()
00130 
00131   Type actualType( ) const { return type(); }
00132   // overrides FGGroupRep::actualType();
00133 
00134 //
00135 // Methods dealing with the properties of the group:
00136 //
00137 
00138   int order( ) const;
00139   Trichotomy isTrivial( ) const;
00140   Trichotomy isFinite( ) const;
00141   Trichotomy isInfinite( ) const;
00142   Trichotomy isAbelian( ) const;
00143   virtual Trichotomy isFree( ) const;
00144   bool compare( const GroupRep* G ) const;
00145 
00146 //
00147 // I/O:
00148 //
00149   
00150   void printOn(ostream&) const;
00151   GroupRep* readFrom(istream&, Chars&) const;
00152 
00153   virtual void printRelators(ostream&) const;
00154 
00155 //
00156 // Methods dealing with group elements: //@rn move many to .C
00157 //
00158   
00159   // Iherited from FGGroupRep:
00160   // virtual Elt makeIdentity( ) const;
00161   // virtual Bool isSyntacticIdentity( const Elt& e) const;
00162 
00163   virtual Trichotomy isTrivialElt( const Elt& e ) const {
00164 
00165         return wordProblem(e);
00166   }
00167   // @stc see bugs in the banner
00168 
00169   Trichotomy areEqual(const Elt& e1, const Elt& e2) const {
00170          return wordProblem( multiply( e1, e2.inverse() ) );
00171   }
00172 
00173   // Inherited from FGGroupRep:
00174   // virtual Elt firstElt( ) const;
00175   // virtual Elt nextElt( const Elt& e ) const;
00176   // virtual Elt multiply( const Elt& e1, const Elt& e2 ) const;
00177   // virtual Elt inverseOf( const Elt& e ) const;
00178   // virtual Elt raiseToPower(const Elt&, int) const;
00179   // virtual Elt conjugateBy(const Elt&, const Elt&) const;
00180   // virtual Elt commutator(const Elt&, const Elt&) const;
00181 
00182   Elt eval( const Word& w ) const {
00183          
00184     #if SAFETY > 0
00185            if ( ord(w.maxOccurringGenerator()) > theNumberOfGenerators )
00186                   error("tried to evaluate Word with no interpretation in FreeGroup");
00187     #endif
00188                 return w.freelyReduce(); //@rn appropriate?
00189   }
00190   // overrides FGGroupRep::eval()
00191 
00192 
00193   Trichotomy wordProblem( const Word& w ) const {
00194          return dontknow;
00195   }
00196   // overrides FGGroupRep::wordProblem()
00197 
00198   Trichotomy conjugacyProblem( const Word& u, const Word& v ) const {
00199          return DONTKNOW;
00200   }
00201   // overrides FGGroupRep::conjugacyProblem()
00202 
00203   Word shortenByRelators(const Word& w) const;
00204 
00205   Chars productOfCommutators(const Word& w,File& file);
00206   
00207   Chars productOfSquares(const Word& w,File& file);
00208   
00209   Integer decideOrder(FPGroupRep* Gr) const;
00210   //@rn very temporary
00211 
00212   /////////////////////////////////////////////////////////////////////////
00213   //                                                                     //
00214   // IPC tools:                                                          //
00215   //                                                                     //
00216   /////////////////////////////////////////////////////////////////////////
00217     
00218   inline void write( ostream& ostr ) const
00219   {
00220     FGGroupRep::write(ostr);
00221     ostr < relators;
00222     ostr < isMetricSmallCancellation;
00223     ostr < '\n'; //@dp temp
00224   }
00225 
00226   inline void read( istream& istr )
00227   {
00228     FGGroupRep::read(istr);
00229     istr > relators;
00230     istr > isMetricSmallCancellation;
00231   }
00232 
00233 // Data members:
00234 
00235   SetOf<Word> relators;
00236 
00237 
00238   // Trichotomy isMetricSmallCancellation; // @stc
00239   //@rn
00240   // a) For what lambda?
00241   // b) Requires constructing symmetrized set of relators.
00242   //    Leave this group's relator set symmetrized for subsequent calls
00243   //    to shortenByRelators (which means Dehn's algorithm in this case)?
00244   //    How to protect them from alteration?
00245   // @stc presumably, to know isMetricSmallCancellation, lambda must be
00246   // computed; therefore, lambda should be stored, and this should
00247   // test the value of lambda. The relators can't be enhanced, since
00248   // that would make this group formally another group, ie. surprise
00249   // for the user. The question remains open whether and how a group
00250   // should keep alternative representations for itself.
00251 
00252   class MetricSmallCancellationLambda {
00253   // simple helper class, flagging the small cancellation property and
00254   // simultanously storing the lambda value; increases consistency,
00255   // reduces memory consumption
00256     int lambda_val;
00257         // @stc tentative internal coding convention:
00258         // -1: DONTKNOW (initial value);
00259         //  1: NO (not a small cancellation group);
00260         //  0: lambda is infinite;
00261         //  2: the value of lambda.
00262   public:
00263         MetricSmallCancellationLambda( ) : lambda_val(dontknow) { }
00264         MetricSmallCancellationLambda( int l ) : lambda_val(l) { }
00265 
00266  /////////////////////////////////////////////////////////////////////////
00267   //                                                                     //
00268   // IPC tools:                                                          //
00269   //                                                                     //
00270   /////////////////////////////////////////////////////////////////////////
00271 
00272   friend ostream& operator < ( ostream& ostr, const MetricSmallCancellationLambda& iMSC)
00273   {
00274     ostr < iMSC.lambda_val;
00275     return ostr;
00276   } 
00277   
00278   friend istream& operator > ( istream& istr, MetricSmallCancellationLambda& iMSC )
00279   {
00280     istr > iMSC.lambda_val;
00281     return istr;
00282   }
00283 
00284     Trichotomy operator()( ) const {
00285       switch (lambda_val) {
00286                 case dontknow: return DONTKNOW;
00287         case  1: return NO;
00288                 default: return YES;
00289           }
00290         }
00291         int lambda( ) const {
00292                 #if SAFETY > 0
00293                 if (lambda_val < 0) error("Tried to take undefined lambda in"
00294                         " FPGroupRep::MetricSmallCancellationLambda::lambda()");
00295                 #endif
00296                 return lambda_val;
00297         }
00298         void setLambda( int l ) {
00299                 #if SAFETY > 0
00300         if (l < 0) error("Tried to set bad lambda in"
00301             " FPGroupRep::MetricSmallCancellationLambda::setLambda()");
00302         #endif
00303         lambda_val = l;
00304         }
00305         void reset( ) { lambda_val = dontknow; }
00306         enum { dontknow = -1, infinity = 0 }; // export constants
00307         // @stc it might be preferable to make dontknow and infinity
00308         // class objects or classes themselves.
00309   };
00310 
00311   MetricSmallCancellationLambda isMetricSmallCancellation;
00312   // flags the property and stores the value of lambda at the same time
00313 
00314 };
00315 
00316 #endif
00317 

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