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

/magnus/back_end/NilpotentGroup/include/MalcevSet.h

Go to the documentation of this file.
00001 // Copyright (C) 1994 The New York Group Theory Cooperative
00002 // See magnus/doc/COPYRIGHT for the full notice.
00003 
00004 // Contents: Definition of MalcevSet class.
00005 //
00006 // Principal Author: Eugene Paderin
00007 //
00008 // Status: Draft
00009 //
00010 // Description:
00011 //
00012 //   This is a helper structure for SGOfFreeNilpotentGroup class.
00013 //   The subgroup is defined by giving set of words. This set is
00014 //   further extended and brought to special form in order to 
00015 //   find the Mal'cev basis of the subgroup. Class MalcevSet keeps
00016 //   the generating words and maintains all the set transformations.
00017 //
00018 // Special Notes:
00019 //
00020 //
00021 // Revision History:
00022 //
00023 
00024 #ifndef _MALCEV_SET_H_
00025 #define _MALCEV_SET_H_
00026 
00027 #include "NilpotentCollector.h"
00028 #include "QuickAssociations.h"
00029 #include "AbelianGroup.h"
00030 
00031 //================================================================
00032 //------------------- MalcevSet ----------------------------------
00033 //================================================================
00034 
00035 // The class is based on QuickAssociations. The key is theWord.leader()
00036 
00037 class MalcevSet {
00038 
00039 public:
00040   
00041   //-----------------------------------------------------
00042   //   Constructors  
00043   //-----------------------------------------------------
00044 
00045   MalcevSet();
00046   // just a placeholder
00047 
00048   MalcevSet(const VectorOf<Word>& v, const NGCollector& nc);
00049   // put the words to the set
00050   // ** Time-consuming
00051 
00052   // copy constructor and destructor provided by compiler
00053 
00054 
00055   //-----------------------------------------------------
00056   //   Accessors 
00057   //-----------------------------------------------------
00058 
00059 
00060   int cardinality() const { return theSet.cardinality(); }
00061   // returns number of elements currently in the basis
00062 
00063   bool isMalcevBasis() const { return isBasis; }
00064   // returns true if the set is proved to be Malcev basis
00065   //@ep some semantical imperfectness: here 'false' really means 'dontknow'.
00066 
00067   bool isNormalClosure() const;
00068   // returns true if the basis is normal closure
00069   // The set must be Malcev basis 
00070   // ** Time-consuming
00071 
00072 
00073   //-----------------------------------------------------
00074   //   Methods to form the set
00075   //-----------------------------------------------------
00076 
00077   // assignment operator provided by compiler
00078 
00079   void makeFull() const; // logical const !
00080   // makes the set to be the Malcev basis of the subgroup
00081   // Slow
00082 
00083   MalcevSet normalClosure() const;
00084   // makes the normal closure of the set
00085   // Slow
00086 
00087 
00088   AbelianGroup mapToQuotient(int weight) const;
00089   // maps the subgroup generated by the set to the quotient 
00090   // G_weight / G_{weight+1}
00091   // Slow, the set must be full
00092   // The result is initialized (cyclic decomposition found)
00093 
00094 
00095   //-----------------------------------------------------
00096   //   Word containment problem
00097   //-----------------------------------------------------
00098 
00099 
00100   bool contains(const Word& w) const;
00101   // returns true iff the word is a member of the set
00102   // ** Time-consuming
00103 
00104   bool decomposeWord(const PolyWord& w, PolyWord& decomp) const;
00105   // if w is an element of the subgroup, computes its decomposition;
00106   // if not, decomp is empty word
00107   // returns true iff the word can be decomposed
00108   // ** Time-consuming
00109 
00110 
00111   //-----------------------------------------------------
00112   //   Conversions to other presentations
00113   //-----------------------------------------------------
00114 
00115 
00116   VectorOf<Word> getWords() const;
00117   // returns the basis as a vector of words in terms of
00118   // the group generators
00119 
00120   VectorOf<Word> getCommutatorWords() const;
00121   // returns the basis as a vector of words in terms of
00122   // the basic commutators
00123 
00124   VectorOf<PolyWord> getPolyWords() const;
00125   // returns the basis as a vector of PolyWords
00126 
00127 
00128   //-----------------------------------------------------
00129   //   I/O
00130   //-----------------------------------------------------
00131 
00132 
00133   void printOn(ostream& s) const;
00134 
00135   friend ostream& operator < (ostream& s, const MalcevSet& b);
00136   // IPC output
00137 
00138   friend istream& operator > (istream& s, MalcevSet& b);
00139   // IPC intput
00140 
00141 
00142   //-----------------------------------------------------
00143   //   Helper methods
00144   //-----------------------------------------------------
00145 
00146 private:
00147 
00148   bool reduceWords(PolyWord& mw1, PolyWord& mw2) const;
00149   // Reduces two words
00150   // After reduction the leading term of mw1 is in minimal power,
00151   // the leading term of mw2 is greater.
00152   // Returns true iff mw1 was changed
00153   // ** Time-consuming
00154 
00155   static PolyWord makeCommutator( PolyWord& mw1, PolyWord& mw2 );
00156   // produces commutator of two words
00157 
00158   static int power(const PolyWord& pw) { 
00159     if( pw.isEmpty() ) return 0;
00160     return pw.firstLetter().power;
00161   }
00162   // power
00163 
00164   static int absPower(const PolyWord& pw) { 
00165     if( pw.isEmpty() ) return 0;
00166     return abs( pw.firstLetter().power );
00167   }
00168   // absolute power :)
00169 
00170   static Generator leader(const PolyWord& pw) {
00171     if( pw.isEmpty() ) return 1;
00172     return pw.firstLetter().gen;
00173   }
00174   //the leading letter of the collected form
00175 
00176   static int sign(const PolyWord& pw) {
00177     if( pw.isEmpty() ) return 0;
00178     return pw.firstLetter().power > 0 ? 1 : 0;
00179   }
00180   // The sign of the leader power
00181 
00182   PolyWord collect(const PolyWord& pw) const {
00183     return theCollector.collect(pw);
00184   }
00185 
00186   void checkMembership(PolyWord& w) const;
00187   // checks whether w can be presented as an admissible set of exponents.
00188   // returns the "remainder"
00189   // The argument must be collected
00190   // ** Time-consuming
00191 
00192   bool addWord(const Word& w);
00193   // adds w to the set
00194   // returns true iff the set was changed
00195   // ** Time-consuming
00196 
00197   bool addWord(const PolyWord& w);
00198   // returns true iff the set was changed
00199   // ** Time-consuming
00200 
00201   void makeNormalClosure();
00202   // makes the set to be normally closed
00203   // ** Time-consuming
00204 
00205   //-----------------------------------------------------
00206   //   Data
00207   //-----------------------------------------------------
00208 
00209 private:
00210 
00211   QuickAssociationsOf<Generator, PolyWord> theSet;
00212   bool isBasis;
00213   Trichotomy isNormal;
00214   NGCollector theCollector;
00215 
00216   friend class FPNilpotentGroupRep;
00217   friend class SGOfFreeNilpotentGroupRep;
00218 
00219 };
00220 
00221 #endif

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