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

/magnus/back_end/Equations/include/NielsenTransformations.h

Go to the documentation of this file.
00001 // Copyright (C) 1995 The New York Group Theory Cooperative
00002 // See magnus/doc/COPYRIGHT for the full notice.
00003 
00004 // Contents: Definition and implementation of regular (x -> xy)
00005 //           and singular (x -> 1) Nielsen transformations (classes
00006 //           ElementaryRegularAuto, RegularAuto, ElementarySingularEndo, 
00007 //           SingularEndo)
00008 //
00009 // Principal Authors: Eugeny Paderin, Dmitry Pechkin
00010 //
00011 // Status: in progress
00012 //
00013 // Revision History:
00014 //
00015 // Special remarks:
00016 //
00017 // * We implemented this for our internal needs only. To achieve
00018 //   better reusability, many improvements must be done. For example,
00019 //   when we multiply regular automorphisms, we only concatenate
00020 //   lists, not trying to reduce inverse neighbors.
00021 //
00022 // * Again, we didn't need transformations x -> x^-1, so we didn't
00023 //   consider them. So we call an automorphism regular iff it consists
00024 //   of elementary transformations of type x -> xy.
00025 //
00026 
00027 
00028 #ifndef _NIELSEN_TRANSFORMATIONS_H_
00029 #define _NIELSEN_TRANSFORMATIONS_H_
00030 
00031 #include "Set.h"
00032 #include "List.h"
00033 #include "Word.h"
00034 #include "Automorphism.h"
00035 
00036 ////////////////// ElementaryRegularAuto /////////////////////////////////
00037 
00038 class ElementaryRegularAuto
00039 {
00040   // data members
00041 
00042   Generator g, g1, g2;
00043 
00044         // We store the transformation in form g -> g1*g2, when g is
00045         // always of "positive order" (acoording to its digital value).
00046         // Instead, we could represent it with only two generators,
00047         // meaning g1 -> g1*g2. The current representation was chosen
00048         // mainly due to imperfection of Word::replaceGeneratorWithWord
00049         // (it works only when generator is "positive"). It can be easily
00050         // changed.
00051 
00052 public:
00053 
00054   // constructors
00055 
00056   ElementaryRegularAuto(const Generator& x, const Generator& y)
00057     : g(x), g1(x), g2(y) 
00058   {
00059 #if SAFETY > 0
00060     if( x == y || x == ::inv(y) )
00061       error("Bad parameters in calling "
00062             "ElementaryRegularAuto::ElementaryRegularAuto(x,y) "
00063             " - not an automorphism");
00064 #endif
00065 
00066     if( ord(x) < 0 ) {
00067       g  = ::inv(x);
00068       g1 = ::inv(y);
00069       g2 = g;
00070     }
00071   }
00072   // x -> xy
00073 
00074   // copy constructor, operator=, and destructor supplied by compiler
00075 
00076 
00077   // accessors
00078 
00079   Generator x() const { return (g == g1? g  : ::inv(g)); }
00080   Generator y() const { return (g == g1? g2 : ::inv(g1)); }
00081 
00082   // methods
00083 
00084   inline friend bool operator==(const ElementaryRegularAuto& u, 
00085                                 const ElementaryRegularAuto& w) 
00086   {     return ( u.g == w.g && u.g1 == w.g1 && u.g2 == w.g2);   }
00087 
00088   ElementaryRegularAuto inv() const {
00089     if( g == g1 )
00090       return ElementaryRegularAuto(g, ::inv(g2));
00091     else
00092       return ElementaryRegularAuto(::inv(g), g1);
00093   }
00094 
00095   Word imageOf(const Word& w) const 
00096   {     return w.replaceGeneratorWithWord(g, g1*g2); }
00097 
00098   Word operator()(const Word& w) const
00099   { return imageOf(w); }
00100   // operator synonym of imageOf.
00101 
00102 };
00103 
00104 inline bool operator!=(const ElementaryRegularAuto& u, const ElementaryRegularAuto& w) {
00105   return !(u == w);
00106 }
00107 
00108 ///////////////// RegularAuto ////////////////////////////////////////
00109 
00110 class RegularAuto
00111 {
00112   // data members
00113 
00114   ListOf<ElementaryRegularAuto> autoList;
00115 
00116 public:
00117 
00118   // constructors
00119 
00120   RegularAuto() {} // is treated as identity automorphism
00121   RegularAuto(const ElementaryRegularAuto& a) : autoList(a) {}
00122   RegularAuto(const ListOf<ElementaryRegularAuto>& list) : autoList(list) {}
00123 
00124   // copy constructor and destructor supplied by compiler
00125 
00126 
00127   // accessors
00128 
00129   ListOf<ElementaryRegularAuto> getAutoList() const { return autoList; }
00130 
00131   // methods
00132 
00133   RegularAuto inv() const {
00134     ListOf<ElementaryRegularAuto> invAutoList;
00135     ListIterator< ListOf<ElementaryRegularAuto> > I(autoList);
00136     while( !I.done() ) {
00137       invAutoList.prepend( I.value().inv() );
00138       I.next();
00139     }
00140     return RegularAuto(invAutoList);
00141   }
00142 
00143   Word imageOf(const Word& w) const {
00144     Word u = w;
00145     ListIterator< ListOf<ElementaryRegularAuto> > I(autoList);
00146     while( !I.done() ) {
00147       u = I.value().imageOf(u).freelyReduce();
00148       // the word is freely reduced to avoid
00149       // its overgrowth (exponential!) when
00150       // the autoList is long enough
00151       I.next();
00152     }
00153     return u;
00154   }
00155 
00156   inline friend bool operator==(const RegularAuto& u, const RegularAuto& w) {
00157     return (u.autoList == w.autoList);
00158   }
00159   // the comparison is unsatisfactory because we don't reduce
00160   // inverse pairs. We didn't need this method...
00161 
00162   Automorphism makeAutomorphism(const FGGroup& G) const {
00163     Automorphism M(G);
00164 
00165     int numOfGens = G.numberOfGenerators();
00166     for(int i=0; i<numOfGens; i++)
00167       M.setGeneratingImages( i, imageOf(Generator(i+1)) );
00168     return M;
00169   }
00170   // converts the given RegularAuto into Automorphism acting on
00171   // group G
00172 };
00173 
00174 //////////////////////////////////////////////////////////////////////
00175 
00176 // Functions related to RegularAuto
00177 
00178 inline Word operator | (Word& w, ElementaryRegularAuto& era) {
00179   return era.imageOf(w);
00180 }
00181 
00182 inline Word operator | (const Word& w, const RegularAuto& ra) {
00183   return ra.imageOf(w);
00184 }
00185 
00186 inline RegularAuto operator | (const RegularAuto& ra1, const RegularAuto& ra2)
00187 {       return RegularAuto(concatenate(ra1.getAutoList(),ra2.getAutoList())); }
00188 
00189 
00190 ////////////// ElementarySingularEndo //////////////////////////////////
00191 
00192 class ElementarySingularEndo
00193 {
00194 public:
00195   // data members
00196 
00197   Generator g;
00198 
00199   // constructors
00200 
00201   ElementarySingularEndo(const Generator& G) : g(abs(ord(G))) {}
00202   // g -> 1
00203 
00204   // accessors:
00205 
00206   Generator gen() const { return g; }
00207 
00208   // methods:
00209 
00210   Word imageOf(const Word& w) const {
00211     return w.replaceGeneratorWithWord(g, Word());
00212   }      // the word IS NOT freely reduced!
00213 
00214   inline friend bool operator==(const ElementarySingularEndo& u, 
00215                                 const ElementarySingularEndo& w) 
00216   { return (u.g == w.g); }
00217 
00218 };
00219 
00220 inline Word operator | (const Word& w, const ElementarySingularEndo& ese) 
00221 { return ese.imageOf(w); }
00222 
00223 
00224 ///////////////// SingularEndo //////////////////////////////////////
00225 
00226 class SingularEndo
00227 {
00228   // data members
00229 
00230   SetOf<Generator> genSet;
00231 
00232 public:
00233 
00234   // constructors
00235 
00236   SingularEndo() {}  // empty set is treated as identity
00237 
00238   SingularEndo(const ElementarySingularEndo& ese) : genSet(ese.gen()) {}
00239 
00240   SingularEndo(const SetOf<Generator>& set) : genSet(set) {}
00241 
00242   // accessors
00243 
00244   SetOf<Generator> generators() const { return genSet; }
00245 
00246   // methods
00247 
00248   bool isSpecializationOf(const SingularEndo& second) const 
00249   { return genSet.contains(second.genSet); }
00250   // true iff the endo is a specialization of the second one
00251 
00252   friend SingularEndo operator | (const SingularEndo& se1, 
00253                                   const SingularEndo& se2) 
00254   { return SingularEndo( se1.generators() | se2.generators() ); }
00255 
00256   Word imageOf(const Word& w) const {
00257     Word emptyWord;
00258     VectorOf<Word> images(ord(w.maxOccurringGenerator()));
00259     for(int i=0; i<images.length(); i++) {
00260       if( genSet.contains(Generator(i+1)) ) images[i] = emptyWord;
00261       else images[i] = Word(Generator(i+1));
00262     }
00263     return w.replaceGenerators(images);
00264   }
00265 
00266   Endomorphism makeEndomorphism(const FGGroup& G) const {
00267     Word emptyWord;
00268     VectorOf<Word> images(G.numberOfGenerators());
00269     for(int i=0; i<images.length(); i++) {
00270       if( genSet.contains(Generator(i+1)) ) images[i] = emptyWord;
00271       else images[i] = Word(Generator(i+1));
00272     }
00273     return Endomorphism(G, images);
00274   }
00275 
00276   inline friend bool operator==(const SingularEndo& u, const SingularEndo& w) {
00277     return (u.genSet == w.genSet);
00278   }
00279 };
00280 
00281 
00282 inline Word operator | (const Word& w, const SingularEndo& se) {
00283   return se.imageOf(w);
00284 }
00285 
00286 // ostream routines
00287 
00288 inline ostream& operator <<(ostream& o, const ElementaryRegularAuto& era) {
00289   o << era.x() << " -> " << era.x() << " " << era.y();
00290   return o;
00291 }
00292 
00293 inline ostream& operator <<(ostream& o, const RegularAuto& ra) {
00294   o << ra.getAutoList() << endl;
00295   return o;
00296 }
00297 
00298 inline ostream& operator <<(ostream& o, const ElementarySingularEndo& era) {
00299   o << era.gen() << " -> 1 ";
00300   return o;
00301 }
00302 
00303 inline ostream& operator <<(ostream& o, const SingularEndo& ra) 
00304 {
00305   SetIterator<Generator> I(ra.generators());
00306   Generator maxGen = 1;
00307   while( !I.done() ) {
00308     if( I.value() > maxGen ) maxGen = I.value();
00309     I.next();
00310   }
00311   o << " { ";
00312   for(int gen = 1; gen <= maxGen; gen++)
00313     if( ra.generators().contains(Generator(gen)) ) o << Generator(gen);
00314   o << " } -> 1";
00315   return o;
00316 }
00317 
00318 #endif

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