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

/magnus/back_end/AProducts/include/APofFreeGroupsRep.h

Go to the documentation of this file.
00001 //
00002 // $Id: APofFreeGroupsRep.h,v 1.4 1998/01/06 20:03:57 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: Definition of the AmalgProductOfFreeGroupsRep class.
00009 //           The name is abbreviated to fit in a library.
00010 //
00011 // Principal Authors: Eugene Paderin, Dmitry Pechkin
00012 //
00013 // Status: draft
00014 //
00015 // Revision History:
00016 //
00017 // Discussion:
00018 //
00019 // Bugs:
00020 //
00021 //
00022 // Special Notes:
00023 //
00024 //
00025 
00026 #ifndef _AMPRODUCT_FREE_GROUPS_REP_H_
00027 #define _AMPRODUCT_FREE_GROUPS_REP_H_
00028 
00029 #include "FPGroupRep.h"
00030 #include "FreeGroup.h"
00031 #include "VectorPtr.h"
00032 #include "SGofFreeGroup.h"
00033 #include "AP-fixups.h"
00034 #include "Automorphism.h"
00035 
00036 enum NumberOfFactor { LEFT_FACTOR = 0, RIGHT_FACTOR = 1, PRODUCT, INTERSECTION };
00037 // This value indicates word membership. LEFT_FACTOR or RIGHT_FACTOR
00038 // mean that the word consists entirely of generators of one factor,
00039 // INTERSECTION means that the word belongs to the amalgamated subgroup
00040 // and thus can be written in generators of any factor, and PRODUCT means
00041 // the other cases.
00042 
00043 //-------------------- LocalWord -------------------------------------
00044 
00045 // A helper class: the word written in generators of one factor,
00046 // together with the factor number.
00047 //
00048 // To understand the concept of local and global words, see comments in
00049 // AmalgProductOfFreeGroups.h header.
00050 
00051 struct LocalWord
00052 {
00053   // methods
00054 
00055   LocalWord() : theWord(), theFactor(INTERSECTION) {}
00056 
00057   LocalWord(const Word& w, const NumberOfFactor& fac) : theWord(w),
00058   theFactor(fac) {}
00059 
00060   // copy constructor, operator= and destructor supplied by compiler
00061 
00062   operator Word() const { return theWord; }
00063 
00064   friend LocalWord operator * (const LocalWord& w1, const LocalWord& w2);
00065 
00066   LocalWord& operator *= (const LocalWord& w) {
00067     return *this = *this * w;
00068   }
00069 
00070   LocalWord inverse() const {
00071     return LocalWord(theWord.inverse(), theFactor);
00072   }
00073 
00074   LocalWord freelyReduce() const {
00075     return LocalWord(theWord.freelyReduce(), theFactor);
00076   }
00077 
00078   // data members
00079 
00080   Word theWord;
00081   NumberOfFactor theFactor;
00082 };
00083 
00084 
00085 //---------------- Class AmalgProductOfFreeGroupsRep ------------------
00086 
00087 struct AmalgProductOfFreeGroupsRep : FPGroupRep {
00088 
00089 // Constructors:
00090 
00091   // Copy constructor and operator= provided by compiler (do deep copy).
00092 
00093   AmalgProductOfFreeGroupsRep(const FreeGroup& g1, const FreeGroup& g2,
00094                               const VectorOf<Word>& gen1, const VectorOf<Word>& gen2 );
00095 
00096   AmalgProductOfFreeGroupsRep(const SGofFreeGroup& sg1,
00097                               const SGofFreeGroup& sg2);
00098 
00099   // Destructor provided by compiler
00100 
00101 // Accessors / Manipulators:
00102 
00103   // Inherited:
00104   // virtual SetOf<Word>& setRelators( const SetOf<Word>& r );
00105   // virtual SetOf<Word>& addRelators( const SetOf<Word>& r );
00106   // virtual SetOf<Word>& removeRelators( const SetOf<Word>& r );
00107 
00108 //
00109 // Representation methods:
00110 //
00111 
00112   PureRep* clone( ) const { return new AmalgProductOfFreeGroupsRep(*this); }
00113   // overrides FGGroupRep::clone()
00114 
00115   static const Type theAmalgProductOfFreeGroupsType;
00116 
00117   static Type type( ) { return theAmalgProductOfFreeGroupsType; }
00118   // dominates FPGroupRep::type()
00119 
00120   Type actualType( ) const { return type(); }
00121   // overrides FPGroupRep::actualType();
00122 
00123 
00124 //
00125 // Methods dealing with the properties of the group:
00126 //
00127 
00128   int order( ) const;
00129   // Overrides FPGroupRep::order().
00130 
00131   Trichotomy isTrivial( ) const;
00132   // Overrides FPGroupRep::isTrivial().
00133 
00134   Trichotomy isFinite( ) const;
00135   // Overrides FPGroupRep::isFinite().
00136 
00137   Trichotomy isInfinite( ) const;
00138   // Overrides FPGroupRep::isInfinite().
00139 
00140   Trichotomy isAbelian( ) const;
00141   // Overrides FPGroupRep::isAbelian().
00142 
00143   Trichotomy isFree( ) const;
00144   // Overrides FPGroupRep::isFree().
00145 
00146   Trichotomy isHyperbolic() const;
00147   // Determines whether given group is hyperbolic.
00148 
00149 //
00150 // I/O:
00151 //
00152 
00153   void printOn(ostream&) const;
00154   // Overrides FPGroupRep::printOn().
00155 
00156   GroupRep* readFrom(istream&, Chars&) const;
00157   // Overrides FPGroupRep::readFrom().
00158 
00159   void printRelators(ostream&) const;
00160   // Overrides FPGroupRep::printRelators().
00161 
00162   void printDecomposition(ostream& ostr, const VectorOf<Word>& deco) const;
00163   // Prints given vector of words in follow format: words are separated
00164   // by dot.
00165   
00166 
00167 //
00168 // Methods dealing with group elements:
00169 //
00170 
00171   Elt eval( const Word& w ) const {
00172 #if SAFETY > 0
00173     if ( ord(w.maxOccurringGenerator()) > theNumberOfGenerators )
00174       error("tried to evaluate Word with no interpretation in FreeGroup");
00175 #endif
00176     return reducedFormOf(w);
00177   }
00178   // Overrides FGGroupRep::eval().
00179 
00180 
00181   Trichotomy wordProblem( const Word& w ) const {
00182     return ( reducedFormOf(w).length() == 0 ? yes : no );
00183   }
00184   // Overrides FGGroupRep::wordProblem().
00185 
00186   NumberOfFactor factorOfFormalWord(const Word& w) const;
00187   // Determines the group the given formal word belongs to.
00188 
00189   NumberOfFactor factorOfElement(const Word& w) const;
00190   // Same as above, but also checks whether the given element of
00191   // the product belongs to the amalgamated subgroup.
00192 
00193   VectorOf<Word> decompose(const Word& w) const;
00194   // Decomposes the given word to the product of words d_1 d_2 ....
00195   // such that every d_i belongs to one of the factors and any
00196   // two successive words belong to distinct factors.
00197 
00198   VectorOf<Word> reducedDecomposition(const Word& w) const;
00199   // Find the minimal (in the sense of number of components) decomposition
00200   // of the given word.
00201 
00202   Word reducedFormOf(const Word& w) const {
00203     return compose(reducedDecomposition(w));
00204   }
00205   // As above, but result is presented as a single word.
00206 
00207   VectorOf<Word> normalDecomposition(const Word& w) const;
00208   // Finds the normal decomposition of the given word: this is
00209   // the reduced decomposition where all components except the
00210   // first one are some right Schreier representatives.
00211   //
00212 
00213   Word normalFormOf(const Word& w) const {
00214     return compose(normalDecomposition(w));
00215   }
00216   // As above, but result is presented as a single word.
00217 
00218   int lengthOf(const Word& w) const { return decompose(w).length(); }
00219   // Compute the length of word decomposition.
00220 
00221   int numberOfSubstitutions( const Word& w ) const;
00222   // If the given word represents 1 in the group
00223   // the function computes the number of uses of a relation
00224   // a = b to deduce that w = 1, i.e. in re-expressing w as 
00225   // a product of conjugates of a * b^-1, computes the number
00226   // of these conjugates.
00227 
00228   //
00229   // Local coding word <--> global coding word conversions.
00230   //
00231 
00232   Word localToGlobal(const LocalWord& w) const {
00233     return localToGlobal(w.theWord, w.theFactor);
00234   }
00235   // Convert local coding word into global coding one.
00236 
00237   Word localToGlobal(const Word& theWord, NumberOfFactor theFactor) const;
00238   // Convert local word presented by word and factor into the global 
00239   // coding one.
00240 
00241   LocalWord globalToLocal(const Word& w) const;
00242   // Convert global coding word into local coding one.
00243 
00244 
00245   NumberOfFactor factorOfGenerator(const Generator& gen) const {
00246     if( abs(ord(gen)) <= numerationShift )
00247       return LEFT_FACTOR;
00248     else
00249       return RIGHT_FACTOR;
00250   }
00251   // Determine whether gen is a generator of first or second factor.
00252 
00253   LocalWord mapFromSubgroup(const LocalWord& w) const;
00254   // w is an element of associated subgroup (written in generators
00255   // of one factor). The function rewrites it in generators of another
00256   // factor.
00257 
00258   Word mapFromSubgroup(const Word& w) const {
00259     LocalWord lw = globalToLocal(w);
00260     return localToGlobal( mapFromSubgroup(lw) );
00261   }
00262   // The same as above. There is warning: no checking is done for the word `w'
00263   // is actually belongs to the associated subgroup or just one of factors.
00264 
00265   bool isElementOfSubgroup(const LocalWord& w) const;
00266   // Determines whether the given word is an element of associated subgroup.
00267 
00268   LocalWord rightSchreierRepresentativeOf(const LocalWord& w) const;
00269   // Finds right Schreier Representative of given word.
00270 
00271   void makeSubgroupMapping(const VectorOf<Word>& gen1,
00272                            const VectorOf<Word>& gen2);
00273   // Constructs mapping between associated subgroups.
00274   // Used *only* by constructors.
00275 
00276   void fixGeneratorsNames();
00277   // Used *only* by constructors.
00278 
00279   virtual void maximalRoot(const Word& w, Word& root, int& power) const;
00280   // Returns maximal root of given word w and maximal power.
00281   //@dp this method is not implemented yet.
00282 
00283   bool isProperPower(const Word& w) const;
00284   // Determines whether w is a proper power.
00285 
00286   bool isProperPowerOfSecond(const Word& u, const Word& w, int& power) const;
00287   // Determines whether u is a proper power of w.
00288 
00289   bool commute(const Word& u, const Word& w) const;
00290   // Determines whether [u,w] = 1.
00291 
00292   bool isSubgroupTrivial(const VectorOf<Word>& subgrp) const;
00293   // Determines whether subgroup generated by vec is trivial.
00294 
00295   bool isSubgroupCyclic(const VectorOf<Word>& subgrp) const;
00296   // Determines whether subgroup generated by vec is cyclic.
00297 
00298   bool isSubgroupAbelian(const VectorOf<Word>& subgrp) const;
00299   // Determines whether subgroup generated by vec is abelian.
00300 
00301   void cyclicReduction(const Word& w, Word& result, Word& conjugator) const;
00302   // Finds cyclic reduction of w such that w = result^conjugator.
00303 
00304   void cyclicDecomposition(const Word& w, VectorOf<Word>& result, 
00305                            Word& conjugator) const;
00306   // The same as above, but result is represented as vector of components.
00307 
00308   // Data members:
00309 
00310   // These four vectors consist of two elements concerning two factors
00311   // of the product.
00312   VectorPtrOf<FreeGroup> factor;            // [2]
00313   VectorPtrOf<SGofFreeGroup> assocSubgroup; // [2]
00314   VectorPtrOf<Map> subgroupMapping;         // [2]
00315   VectorPtrOf<Automorphism> nielsenBasisToGensOfSubgroup; // [2]
00316   int rankOfSubgroups;
00317 
00318   int numerationShift; // shift in global numeration of the second factor
00319   // subgroupMapping[i] maps i-th factor subgroup into another subgroup
00320   // the word being mapped is written in Nielsen basis of the subgroup,
00321   // *not* in generators of the group. The result is written in
00322   // generators of (the opposite) group.
00323 
00324 };
00325 
00326 #endif
00327 
00328 
00329 

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