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();
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 1.2.6 written by Dimitri van Heesch, © 1997-2001