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

/magnus/back_end/Equations/include/QEqnSolutions.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 class QEqnSolutionsInFreeGroup
00005 //
00006 // Principal Author: Dmitry Pechkin, Eugeny Paderin
00007 //
00008 // Status: Under trial
00009 //
00010 // Description:
00011 //
00012 // * The program works with equations with (and without) quotients.
00013 //   We used algorithm described in [1].
00014 //
00015 // Here is a brief description of Comerford & Edmunds main ideas.
00016 //
00017 // Any solution of W = 1 over group G can be represented as S*P*E,
00018 // where S is an automorphism mapping W to itself (i.e. element of
00019 // stabilizer of W in Aut(G), P is a certain endomorphism from a
00020 // finite set of "basic solutions", and E is any "specializing"
00021 // endomorphism. According to Comerford & Edmunds (C&E), we can
00022 // choose P as some combinations of elementary Nielsen transformations
00023 // (to be exact, elementary regular automorphisms (ERA) x -> xy, not
00024 // lengthening the word, and elementary singular endomorphisms (ESE)
00025 // x -> 1, shortening the word; here x is a variable). In this case,
00026 // instead of stabilizer we can take its regular subset RegStab,
00027 // generated by regular automorphisms (RA).
00028 //
00029 // Let W be a minimal word (i.e. it cannot be shortened by RA). We
00030 // build a graph where vertices are images of W (their number is finite),
00031 // and edges are ERA mapping one word to another. Then elements of
00032 // RegStab are all the reduced paths starting and ending at W; if we
00033 // find some (any) maximal subtree in the graph, then any edge not
00034 // included in the tree defines certain generator of RegStab.
00035 //
00036 // If there is a path (RA) R leading from W to some vertex V, and T
00037 // is a SE mapping V to 1, then TR is a solution of W=1. C&E say
00038 // that all these TR make a set of basic solutions of W=1.
00039 //
00040 // If W is not minimal, then we take the surface form of W that is proved
00041 // to be minimal. C&E say: if V is some minimal image of W
00042 // and N is RA mapping W to V, then solutions of W and V are the same
00043 // up to N. So we can find a stabilizer and basic solutions for V
00044 // and then multiply them to N (if S is a generator of RegStab(V),
00045 // then NSN^-1 is a generator of RegStab(W), and if P is a basic
00046 // solution of V then NP is one of W).
00047 //
00048 // Usage:
00049 //  
00050 //   A brief scheme of usage:
00051 // 
00052 //   QEqnSolutions equation(givenGroup, givenWord, numberOfVariables);
00053 //
00054 //   equation.startComputation();                // initialization
00055 //   while( !equation.isComputationDone() ) {
00056 //     equation.continueComputation();           // do one step
00057 //
00058 //     while( equation.haveNewSolution() ) {     // take found solutions
00059 //       Endomorphism solution = equation.getSolution();
00060 //       // do something with the solution...
00061 //       equation.nextSolution();
00062 //     }
00063 //
00064 //     while( haveNewStabGenerator() ) {         // take found generators
00065 //       Automorphism regStabGen = equation.getStabGenerator();
00066 //       // do something with the generator...
00067 //       equation.nextStabGenerator();
00068 //     }
00069 //   }
00070 //
00071 // References:
00072 //
00073 //   [1]. L.Comerford, C.Edmunds, Solutions of equations in free groups,
00074 //        in Group Theory: proceedings of the Singapore Group Theory
00075 //        Conference held at the National University of Singapore, 
00076 //        June 8-19, 1987.   ISBN 3-11-011366-X.
00077 //
00078 //   [2]. R.I.Grigorchuk, P.F.Kurchanov, On Quadratic Equations in Free
00079 //        groups. Contemporary Mathematics, vol. 131, 1992 (part I),
00080 //        pp. 159-171.
00081 //
00082 // Revision History:
00083 //
00084 // * 10/96 EP added a routine checkEquation.
00085 //   
00086 // Special Notes:
00087 //
00088 // * Costness of algorithm is exponential by number of length of equation
00089 //   (by memory and time requests). So an equation given by the user
00090 //   may not be computed completely, but some basic solutions and generators
00091 //   of regular stabiliser can be obtained by user at the running time,
00092 //   without waiting for complete computation. 
00093 //
00094 // * The algorithm is very general and thus rather slow; in future, some
00095 //   dedicated methods for special cases will be implemented, so the whole
00096 //   structure of the class can be changed considerably.
00097 
00098 #ifndef _QEQN_SOLUTIONS_H_
00099 #define _QEQN_SOLUTIONS_H_
00100 
00101 #include "Word.h"
00102 #include "Vector.h"
00103 #include "Queue.h"
00104 #include "VectorPtr.h"
00105 #include "QuickAssociations.h"
00106 #include "NielsenTransformations.h"
00107 
00108 class QEqnSolutionsInFreeGroup
00109 {
00110 public:
00111 
00112   /////////////////////////////////////////////////////////////////////////
00113   //                                                                     //
00114   // Constructors:                                                       //
00115   //                                                                     //
00116   /////////////////////////////////////////////////////////////////////////
00117 
00118   // no default constructor
00119 
00120   QEqnSolutionsInFreeGroup(const FreeGroup& G, const Word& equation, int numOfVar);
00121   // Construct quadratic equation with given word in given group G
00122   // which is a formal group generated by variables and constants:
00123   // the first numOfVar generators are treated as variables,
00124   // other generators of the group are constants.
00125 
00126   // copy constructor, operator=, and destructor supplied by compiler
00127 
00128   /////////////////////////////////////////////////////////////////////////
00129   //                                                                     //
00130   // Activation members for solving the equation:                        //
00131   //                                                                     //
00132   /////////////////////////////////////////////////////////////////////////
00133 
00134   void startComputation();
00135   void continueComputation();
00136   // These two methods launch and perform process of solving the equation.
00137   // After performing one step, some new basic solutions and generators
00138   // of RegStab are found, and user can require them. 
00139   // Simultaneously the rank of equation is computed,
00140   // but it is available only after the computation is completed.
00141 
00142   void disableBuildingRegStab() { status.enableBuildingRegStab = false; }
00143   void enableBuildingRegStab() { status.enableBuildingRegStab = true; }
00144   // Building of regular stabilizer is enabled by default. User can
00145   // disable this, accelerating performance and saving memory. After disabling,
00146   // all the following steps do not return corresponding generators and
00147   // all related information is lost. So when user disables the RegStab
00148   // building and then enables it again, one loses some generators.
00149 
00150   void disableBuildingSolutions() { status.enableBuildingSolutions = false; }
00151   void enableBuildingSolutions() { status.enableBuildingSolutions = true; }
00152   // The same about building partial solutions.
00153 
00154   /////////////////////////////////////////////////////////////////////////
00155   //                                                                     //
00156   // Status queries:                                                     //
00157   //                                                                     //
00158   /////////////////////////////////////////////////////////////////////////
00159 
00160   bool isComputationDone() const { return computationIsDone; }
00161   // Returns true iff computation is finished.
00162 
00163   bool isComputationStarted() const { return computationIsStarted; }
00164   // Returns true iff `startComputation' have been invoked.
00165 
00166   bool haveNewSolution() const { return solution<theBasicSolutions.length(); }
00167   // Returns true iff at least one new basic solution is available.
00168 
00169   bool nextSolution() { 
00170     if( !haveNewSolution() ) return false;
00171     solution++; 
00172     return true;
00173   }
00174   // Advances pointer to next basic solution, so that getSolution returns it.
00175   // Returns false iff there is no new solution.
00176 
00177   bool haveNewStabGenerator() const 
00178   { return generator<theRegStabGenerators.length(); }
00179   // Returns true iff at least one new generator of RegStab is available.
00180 
00181   bool nextStabGenerator() {
00182     if( !haveNewStabGenerator() ) return false;
00183     generator++;
00184     return true;
00185   }
00186   // Advances pointer to next generator, so that getStabGenerator returns it.
00187   // Returns false iff there is no new generator.
00188         
00189   bool isBuildingSolutionsEnabled() const { 
00190     return status.enableBuildingSolutions; 
00191   }
00192 
00193   bool isBuildingRegStabEnabled() const { 
00194     return status.enableBuildingRegStab; 
00195   }
00196 
00197   //////////////////////////////////////////////////////////////////////
00198   //                                                                  //
00199   // Accessors                                                        //
00200   //                                                                  //
00201   //////////////////////////////////////////////////////////////////////
00202 
00203   Endomorphism getSolution() {
00204     if( !haveNewSolution() )
00205       error("QEqnSolutionsInFreeGroup::getSolution(): attempt to retrieve "
00206             "a new basic solution before it is computed.");
00207     Endomorphism sol = startPath | Endomorphism(theBasicSolutions[solution]);
00208     sol.reduceGenImages();
00209     return sol;
00210   }
00211   // Returns found basic solution.
00212   // @dp This should be const, but Map::operator| is not const.
00213 
00214   Automorphism getStabGenerator() {
00215     if( !haveNewStabGenerator() )
00216       error("QEqnSolutionsInFreeGroup::getStabGenerator(): attempt to retrieve"
00217             " a new RegStab generator before it is computed.");
00218     Automorphism gen = startPath | 
00219       Automorphism(theRegStabGenerators[generator]) | invStartPath; 
00220     gen.reduceGenImages();
00221     return gen;
00222   }
00223   // Returns found generator of RegStab.
00224   // @dp This should be const, but Map::operator| is not const.
00225 
00226   Word surfaceForm() { 
00227     if( !surfaceFormIsComputed ) computeSurfaceForm();
00228     return theSurfaceForm;
00229   }
00230   // Returns a surface form of the equation.
00231   // @dp logically must be const.
00232 
00233   Automorphism toSurfaceForm() { 
00234     if( !surfaceFormIsComputed ) computeSurfaceForm();
00235     return toSurface;
00236   }
00237   // Returns an (regular) automorphism bringing the equation into a surface
00238   // form.
00239   // @dp logically must be const.
00240 
00241   FreeGroup group() const { return theGroup; }
00242   Word equation() const { return theEquation; }
00243   int numberOfVariables() const { return theNumberOfVariables; }
00244   int numberOfGenerators() const { return theNumberOfGenerators; }
00245   int numberOfConstants() const { return theNumberOfGenerators-theNumberOfVariables; }
00246 
00247   int rank() const { return theRank; }
00248   // returns -1 if rank is not computed yet, otherwise non-negative number 
00249   // which is the computed rank of the equation.
00250 
00251   VectorPtrOf<Endomorphism> basicSolutions() const { return theBasicSolutions;}
00252   // Returns all known basic solutions of the equation.
00253   // NB. This function returns `stripped' basic solutions. To get `true'
00254   // solutions the user must append (left) the prefixMap() automorphism.
00255 
00256   VectorPtrOf<Automorphism> regStabGenerators() const { return theRegStabGenerators; }
00257   // Returns all known generators of regular stabilizer of the equation.
00258   // NB. This function returns `stripped' generators. To get proper
00259   // generators the user must conjugate each of them by the prefixMap() 
00260   // automorphism.
00261 
00262   Automorphism prefixMap() const { return startPath; }
00263   // Returns automorphsim bringing the equation into a minimal form.
00264   // The minimal form is not necessary to be identical to the surface 
00265   // (canonic) form.
00266 
00267   struct EquationStatus; // forward declaration.
00268 
00269   EquationStatus getProcessStatus() const { return status; }
00270   // Returns full status of the computation process.
00271 
00272 
00273   Endomorphism eliminator() const { return theEliminator; }
00274 
00275   /////////////////////////////////////////////////////////////////////////
00276   //                                                                     //
00277   // I/O:                                                                //
00278   //                                                                     //
00279   /////////////////////////////////////////////////////////////////////////
00280 
00281   friend ostream& operator << ( ostream&, const QEqnSolutionsInFreeGroup& );
00282   // Outputs all known basic solutions in a form readable by the end user.
00283 
00284   /////////////////////////////////////////////////////////////////////////
00285   //                                                                     //
00286   // Type definitions:                                                   //
00287   //                                                                     //
00288   /////////////////////////////////////////////////////////////////////////
00289 
00290   // Process status structure.
00291 
00292   struct EquationStatus
00293   {
00294     EquationStatus() : enableBuildingSolutions(true), 
00295       enableBuildingRegStab(true), verticesToPass(0), verticesPassed(0), 
00296       loopsToPass(0), loopsPassed(0), totalLengthOfLoops(0) {}
00297 
00298     // copy contsructor, operator=, destructor supplied by compiler.
00299 
00300     // data members:
00301 
00302     bool enableBuildingSolutions;
00303     bool enableBuildingRegStab;
00304     int verticesToPass;
00305     int verticesPassed;
00306     int loopsToPass;
00307     int loopsPassed;
00308     long totalLengthOfLoops;
00309   };
00310 
00311 
00312 private:
00313 
00314   class Edge; // forward declaration
00315 
00316   Bool isVariable(const Generator& g) const { 
00317 #if SAFETY > 0
00318     if( abs(ord(g)) > theNumberOfGenerators )
00319       error("Generator out of bounds in QEqnSolution::isVariable(Generator&)");
00320 #endif
00321     return ( abs(ord(g)) <= theNumberOfVariables ? true : false );
00322   }
00323   // Returns true iff the given generator is a variable.
00324 
00325   bool isConstant(const Generator& g) const {
00326 #if SAFETY > 0
00327     if( abs(ord(g)) > theNumberOfGenerators )
00328       error("Generator out of bounds in QEqnSolution::isConstant(Generator&)");
00329 #endif
00330     return ( abs(ord(g)) > theNumberOfVariables ? true : false );
00331   }
00332   // Returns true iff the given generator is a constant.
00333 
00334 
00335   // METHODS OF TREE BUILDER
00336 
00337   void buildNewVerticesAndLoopsFrom(const Word& vertex);
00338   // Expands tree: builds all `offsprings' the given vertex.
00339 
00340   RegularAuto buildPath(const Word& from, const Word& to);
00341   // Builds a path from one vertex to another within the built subtree.
00342 
00343   RegularAuto buildPathTo(const Word& to);
00344   // Builds path from theEquation to the given word.
00345 
00346   void registerEdge(const Word& source, const ElementaryRegularAuto& edge, 
00347                     const Word& target);
00348   // Tries to include the given edge to the maximal tree. If the edge
00349   // forms a loop it certainly should not include; instead, it places the one
00350   // to the list of loops.
00351 
00352 
00353   // METHODS OF BASIC SOLUTIONS BUILDER
00354 
00355   void buildSolutionsOfOneVertex(const Word& w);
00356   // Builds basic solutions for the given word.
00357 
00358   VectorOf<int> checkProperties(const Word& w);
00359   // Checks for every variable of the group whether it can/must/cannot
00360   // be eliminated in given word
00361 
00362   ListOf<SingularEndo> buildSingulars(const Word& w, const VectorOf<int>& varProperties);
00363   // This procedure immediately builds a graph of eliminations for given word.
00364   // varProperties defines a behavior of every variables of the word.
00365 
00366   void appendNewSolution(ListOf<SingularEndo>& solutions, 
00367                          const SingularEndo& newSolution);
00368   // Includes a new singular solution to the list of solutions, unless it is a
00369   // specialization of one of the list.
00370 
00371 
00372   // METHODS OF RANK EQUATION BUILDER
00373 
00374   int rankOfBasicSolution(const Endomorphism& solution) const;
00375   // Computes rank of the given endomorphism.
00376 
00377   // METHODS OF REGSTAB BUILDER
00378 
00379   void processOneLoop(const Edge& edge);
00380   // Builds a generator of stabilizer by the given edge of graph.
00381 
00382   // METHODS OF SURFACE FORM BUILDER
00383   //@dp these descriptions is not quite fine, more detailed comments
00384   //    to appear.
00385 
00386   void computeSurfaceForm();
00387   // Computes surface form of the equation and an automorphism bringing
00388   // the one to the surface form.
00389 
00390   Word extractSquare(Word& w, int firstLocation, int secondLocation);
00391   // Rewrites given word by extracting square of variable at given locations.
00392 
00393   Word extractPinch(Word& w, int firstLocation, int secondLocation);
00394   // Rewrites given word by extracting pinch of variable at given locations.
00395 
00396   Word extractCommutator(Word& w, int xFirstLocation,   int xSecondLocation, 
00397                          int yFirstLocation);
00398   // Rewrites given word by extracting commutator of variables at given 
00399   // locations.
00400 
00401   int getLocationOfArbitraryVariable(const Word& w, int start, int stop) const;
00402   // Returns location of an arbitrary variable which occurrs in the given 
00403   // non-empty word, otherwise returns -1.
00404 
00405   int getPairOfVariable(Word& w, int& firstLocation, int& secondLocation, 
00406                         bool oppositeOrder) const;
00407 
00408   Word bringToCanonicForm(Word& squares, Word& commutators, Word constants, 
00409                           Word& pinches);
00410   // Last stage of computing a surface form and a surface automorphism.
00411 
00412   /////////////////////////////////////////////////////////////////////////
00413   //                                                                     //
00414   // Data Members:                                                       //
00415   //                                                                     //
00416   /////////////////////////////////////////////////////////////////////////
00417 
00418   Word theEquation;           // the given equation
00419   int theNumberOfGenerators;
00420   int theNumberOfVariables;
00421   FreeGroup theGroup; 
00422 
00423   VectorPtrOf<Automorphism> theRegStabGenerators;
00424   VectorPtrOf<Endomorphism> theBasicSolutions;
00425 
00426   int theRank; // rank of given equation
00427   Word theSurfaceForm; // surface form of the equation
00428   Automorphism toSurface; // auto bringing into surface form
00429 
00430   // Control variables of the process
00431 
00432   bool computationIsStarted;
00433   bool computationIsDone;
00434 
00435   int solution; // number of last retrieved basic solution by the user
00436   int generator; // number of last retieved generator of RegStab by the user
00437 
00438 
00439   Endomorphism theEliminator;
00440   // This endomorphism eliminates variables mapping them to 1. Constants are mapped
00441   // to themselves.
00442 
00443 
00444   // TREE BUILDER PROPERTIES
00445 
00446   // The maximal subtree is represented with pairs (associations) of
00447   // a word (some image of the root) and an edge -- an elementary
00448   // regular transformation mapping the word to its PARENT. So,
00449   // edges in the tree are directed from offsprings to parents,
00450   // and we can easily reconstruct a regular automorphism mapping
00451   // the root to the vertex.
00452   // The tree is stored as associative array because we need fast search 
00453   // of vertices.
00454 
00455   struct Edge {
00456 
00457     // edge of a graph of regular transforms of the equation; includes
00458     // source vertex
00459 
00460     Word vertex;
00461     ElementaryRegularAuto edge;
00462 
00463     Edge() : edge(1,2) {} // `dummy' default constructor for use in Sets
00464 
00465     Edge(const Word& w, const ElementaryRegularAuto& e) : vertex(w), edge(e) 
00466     {}
00467 
00468     friend inline bool operator ==(const Edge& x, const Edge& y) {
00469       return ( x.vertex == y.vertex && x.edge == y.edge );
00470     }
00471 
00472     friend ostream& operator <<( ostream& o, const Edge& E);
00473     // This operator is required by SetOf<Edge> class.
00474     // We don't need it, so prohibit the one.
00475 
00476     int hash() const { return vertex.hash(); }
00477   };
00478 
00479   Automorphism startPath; // an automorhism mapping the initial word into its
00480   // minimal form (root)
00481   Automorphism invStartPath;
00482   Word root;             // current root of the tree
00483   QuickAssociationsOf<Word, ElementaryRegularAuto> maxSubTree;
00484   // maximal subtree of the graph of regular transforms of
00485   // theEquation's minimal form (root).
00486 
00487   QueueOf<Word> newVertices; // new transforms to be proceeded
00488 
00489   QueueOf<Edge> loops; //edges not included into the subtree which define loops
00490 
00491 
00492   // BASIC SOLUTION BUILDER PROPERTIES
00493 
00494   Endomorphism removeVarEndo;
00495   // Endomorphism which removes all variables from a word and leaves
00496   // constants only.
00497   SetOf<Endomorphism> setOfBasicSolutions; 
00498   // Temporary fast access storage of basic solutions to prevent duplicate 
00499   // ones. 
00500 
00501   enum { MUST_BE_MAPPED_TO_ITSELF,
00502          MUST_BE_MAPPED_TO_1,
00503          CAN_BE_MAPPED_TO_1
00504   };
00505   // Behavior of variables of a vertex of the tree when a specialization 
00506   // is searched.
00507 
00508 
00509   // RANK BUILDER PROPERTIES
00510 
00511   int tempRank;
00512   // Make intermediate computed value of rank unavailable for the user
00513   // while computation is incomplete.
00514 
00515   // REGSTAB BUILDER PROPERTIES
00516 
00517   SetOf<Automorphism> regStabSet;
00518   // Generators of RegStab which are already found to prevent duplicate them. 
00519 
00520   // SURFACE FORM BUILDER
00521 
00522   bool surfaceFormIsComputed;
00523 
00524   // CLASS INFORMATION
00525 
00526   EquationStatus status;
00527 
00528 #ifdef DEBUG
00529   void debugPrint( ostream& o ) const;
00530   //friend int main();
00531 #endif
00532 
00533 };
00534 
00535 
00536 // This is a procedure converting Set into Vector. It's a double of
00537 // a makeVectorOf(const ListOf<T>&) from conversions.h and also
00538 // should be placed there.
00539 
00540 template <class T> VectorPtrOf<T> makeVectorPtrOf(const SetOf<T>& S)
00541 {
00542   VectorPtrOf<T> result( S.cardinality() );
00543 
00544   int i = 0;
00545   SetIterator<T> I(S);
00546 
00547   while ( !I.done() ) {
00548     result[i++] = I.value();
00549     I.next();
00550   }
00551 
00552   return result;
00553 }
00554 
00555 
00556 ///////////////@ep added on October1996 /////////////////////////////////////////////
00557 
00558 Chars  checkEquation(const FreeGroup& G, const Word& equation, int numOfVar);
00559 
00560 #endif
00561 

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