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

/magnus/back_end/KB/include/RKBPackage.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: RKBPackage.h,v 1.4 1997/02/03 22:41:21 alex Exp $
00003  */
00004 
00005 // Copyright (C) 1994 The New York Group Theory Cooperative
00006 // See magnus/doc/COPYRIGHT for the full notice.
00007 
00008 // Contents: Definition of RKBPackage class.
00009 //
00010 // Principal Author: Sarah Rees
00011 //
00012 // Status: in progress
00013 //
00014 // Revision History:
00015 //
00016 // XI/94: RN: Repaired violations of encapsulation.
00017 //            Replaced direct linking of named pipes with BlackBox.
00018 //
00019 // Next implementation steps:
00020 //
00021 // * Deal with the many @rn, @rn:@sr, @sr comments here and in RKBPackage.C
00022 
00023 
00024 #ifndef _RKBPackage_H_
00025 #define _RKBPackage_H_
00026 
00027 #include <iomanip.h>
00028 
00029 #include "BlackBox.h"
00030 #include "Vector.h"
00031 #include "Chars.h"
00032 #include "Set.h"
00033 #include "Word.h"
00034 #include "DiffMachine.h"
00035 #include "KBMachine.h"
00036 #include "MagnusHome.h"
00037 #include "WordOrder.h"
00038 
00039 
00040 // RKBPackage is a class associated with a run of the RKBPackage program.
00041 // The constructor creates the 3 necessary files and starts the
00042 // program up. The destructor halts the program and deletes the 3
00043 // files. The program may also be halted and restarted at an intermediate
00044 // stage. 
00045 // Initially the group relations are turned into rewrite rules.
00046 // The function runKB runs a KnuthBendix process on the rules, according
00047 // to certain parameters.
00048 // At any stage, using the rules so far, any word in the group generators
00049 // can be rewritten, or a random process approximates the growth rate of
00050 // the group.
00051 // A KnuthBendixMachine or a WordDifferenceMachine can be initialised on the 
00052 // process, at any stage.
00053 // The first allows word reduction in the group independently of the RKBPackage,
00054 // the second is the first step in the construction of the automata of an 
00055 // automatic group. The word differences themselves can also be computed.
00056 
00057 
00058 class RKBPackage {
00059 public:
00060 
00061   //@rn:@sr Explain what these do.
00062 
00063 
00064   RKBPackage(const VectorOf<Chars>& genNames, const SetOf<Word>& relators) 
00065   : theRKBPackage(Chars("cd ")
00066                                                 + MagnusHome::magnusHome()
00067                                                 + "/back_end/black_boxes/rkbp/bin; ./rkbp"
00068                                                 ),
00069      index(1+genNames.length()),index_inv(1+genNames.length()),
00070      genNumber(2*genNames.length())
00071   {
00072     VectorOf<int> order(2*genNames.length());
00073     for (int i=1;i<=genNames.length();i++){ order[2*i-2]=i; order[2*i-1]= -i;}
00074     WordOrder wsl("ShortLex",order);
00075     initialize(genNames, relators,wsl);
00076   }
00077   // starts up the program rkbp, with the generators and relators of
00078   // a group as input.
00079   // An initial rewrite system is created from the group relations,
00080   // using the shortlex ordering.
00081   // No calculation is yet done with the program.
00082 
00083   RKBPackage(const VectorOf<Chars>& genNames, const SetOf<Word>& relators,
00084     const WordOrder & word_order)
00085   : theRKBPackage(Chars("cd ")
00086                                                 + MagnusHome::magnusHome()
00087                                                 + "/back_end/black_boxes/rkbp/bin; ./rkbp"
00088                                                 ),
00089      index(1+genNames.length()),index_inv(1+genNames.length()),
00090      genNumber(2*genNames.length())
00091   {
00092     initialize(genNames, relators,word_order);
00093   }
00094   ~RKBPackage();
00095   // Takes care of shutting down rkbp, and unlinking temp files/pipes.
00096 
00097   Chars getName() const { Chars s = problemName; return s;}
00098 
00099   void runKB(int MaxLen, int numIterations, int saveLHSLen, int saveRHSLen);
00100 
00101   // The rewrite system currently stored is modified by running the Knuth
00102   // Bendix process with the 4 specified parameters,
00103   // MaxLen, numIterations, saveLHSLen, saveRHSLen.
00104   // The (parameterised) Knuth Bendix process procedes as follows.
00105   // Since it is parameterised it will terminate.
00106   
00107   // All left hand sides of existing rules are compared for
00108   // overlaps. (An overlap is a string of the form abc where
00109   // a,b,c are strings and ab and bc are left hand sides,
00110   // The length of the overlap is defined to be the sum of the lengths
00111   // of the strings a,b, and c.)
00112   // Any overlap of length at most maxLen is reduced in two different ways,
00113   // first using the rule with left hand side ab, and then so
00114   // far as possible using the remaining rules,
00115   // second using the rule with left hand side bc, and then so
00116   // far as possible using the remaining rules.
00117   // If the results are different a new rule is found.
00118   // That rule is saved and existing rules which are direct
00119   // consequences of it are deleted provided the lengths of its
00120   // left and right hand sides are less than the bounds
00121   // saveLHSLen and saveRHSLen.
00122 
00123   // The parameter numIterations determines how many passes are made through
00124   // the set of rules by the Knuth Bendix process. 
00125   // If it is set to -1, the process runs until no
00126   // more overlaps are found of length less than maxLen.
00127 
00128 
00129   float* growthRate(int maxLen, int numTrials, int seed);
00130   // The growth rate of the group is estimated using a random
00131   // procedure. The output is an array of floating point numbers;
00132   // the i-th entry is the estimated number of elements of
00133   // length i in the group. Since this is a random (mean) estimate
00134   // it need not be an integer.
00135   // The estimate is made over a number (numTrials) of trials.
00136   // An integer seed needs to be set.
00137 
00138   void saveToFiles();
00139   // the rewrite system currently stored in the process is saved to files
00140   // so that it may be read by magnus functions and not only accessible
00141   // to the program rkbp.
00142   // The name of the files are predetermined, and are not settable.
00143 
00144   void printRules(ostream& str = cout);
00145   // The rules currently held within the rewrite system are printed
00146   // in a user-readable form.
00147 
00148   void readRule(istream& str, Word& left, Word& right);
00149   // The rewrite rule left->right is read from the stream str.
00150   // This function (together with saveToFiles) is used to transfer the
00151   // rewrite rules from the program rkbp to other magnus functions.
00152   // The rules can only be read from the file (with name rulesFilename())
00153   // to which they have been written by the program rkbp.
00154   // Hence ifstream must have been initialised on the file with that name.
00155 
00156 
00157   void oneOffRewrite(Word& w);
00158   // Using the rkbp itself to reduce a word is possible, but it requires
00159   // telling rkbp to change modes. This is equivalent to the statement:
00160   // { enterRewriteMode(); rewrite(Word& w); quitRewriteMode(); }
00161 
00162   void enterRewriteMode();
00163   // Tells the rkbp to enter rewrite mode. This is preparation for reducing
00164   // more than a few words at once.
00165 
00166   void quitRewriteMode();
00167   // Tells the rkbp to leave rewrite mode.
00168 
00169   void rewrite(Word& w);
00170   // Use this if there are many words to be rewritten.
00171   // Bracket calls to rewrite with enterRewriteMode and quitRewriteMode.
00172   // Do not call other functions from this class between calls to rewrite,
00173   // because the rkbp is in the wrong mode.
00174   // @rn:@sr Check the mode flag in the other functions, and report error.
00175 
00176   SetOf<Word> wordDifferences();
00177   // The set of "word differences" associated with the current rewrite system
00178   // is computed and returned.
00179 
00180   // If u->v is a rewrite rule, then where u(i) is the maximal prefix
00181   // of u of length at most i and v(i) is the maximal prefix of v of length at
00182   // most i, the reudction (according to the rewrite system) of the
00183   // word u(i)^-1*v(i) is defined to be a word difference.
00184   // The set of word differences associated with u->v is defined to be
00185   // the set of all word differences as above for all integers i.
00186   // The set of all word differences associated with the rewrite system is
00187   // the union of all the sets of word differences associated with the rules
00188   // in the system.
00189   
00190   // The set of word differences is relevant to the automatic group algorithms.
00191 
00192   DiffMachine differenceMachine(const SetOf<Word> & differences);
00193 
00194   DiffMachine differenceMachine() {return differenceMachine(wordDifferences());}
00195 
00196   KBMachine KnuthBendixMachine();
00197 
00198   VectorOf<Chars> getGeneratorNames() const { return generatorNames; }
00199 
00200   const char* rulesFilename() const { return rulesFileName; }
00201   // Returns the name of the file in which the rewrite rules discovered by
00202   // the rkbp are stored.
00203   // @rn:@sr Probs with simultaneous access? Encapsulation violation.
00204 
00205   int currentNumOfRules() const { return numRules; }
00206   // Returns the number of rules in the rewrite system currently
00207   // stored by the rkbp.
00208 
00209   Bool isProvedConfluent() const { return provedConfluent;}
00210   // Returns true if the rewrite system currently stored  by the rkbp
00211   // is proved to be confluent. (However it could be confluent without us
00212   // knowing it.)
00213 
00214   Bool rulesReduced(Word * lhs,Word * rhs,int numOfrules); 
00215 
00216   Bool sanityCheck() const { return !error; }
00217   // Returns TRUE iff this RKBPackage is functioning properly.
00218 
00219   Chars getGeneratorName(Generator g) const {
00220      int i = ord(g);
00221      if (i>0) return generatorNames[i-1];
00222      else return(generatorNames[-i-1]+"^-1");
00223   }
00224 
00225 
00226 
00227 private:
00228 
00229   //@rn:@sr Explain what the rest of these are used for.
00230 
00231   // Data members:
00232 
00233   //  state flags:
00234 
00235   Bool error;
00236   // Set TRUE when any error in the rkbp is detected.
00237 
00238   Bool runningProcess;
00239   // Set TRUE when the rkbp is generating rules. @rn:@sr right? Wrong.
00240   // Actually, it reports whether or not the rkbp is actually running or not
00241   // (it might have been aborted). It could be the need for this is removed
00242   // by the existence of sanityCheck - will check this out @sr
00243 
00244   Bool rewriteMode;
00245   // Set TRUE when the rkbp is in rewrite mode.
00246 
00247   Bool filesOutOfDate;
00248   // Some functions read the rules from files, and so need to know if
00249   // the files don't contain the current rules.
00250   // If so they update the files.
00251   Bool provedConfluent;
00252   // Returns true if the rewrite system currently stored  by the rkbp
00253   // is proved to be confluent. (However it could be confluent without us
00254   // knowing it.)
00255 
00256 
00257   int numRules;
00258   int lenLeftMin;
00259   int lenLeftMax;
00260   int lenLeftTotal;
00261   int lenRightMin;
00262   int lenRightMax;
00263   int lenRightTotal;
00264 
00265   char problemName[64];     // Problem name supplied to rkbp
00266 //  char* problemName;     // Problem name supplied to rkbp
00267   char inFileName[64];      // Name of pipe bound to stdin of rkbp
00268   char outFileName[64];     // Name of pipe bound to stdout of rkbp
00269   char rulesFileName[64];   // Name of file to which rkbp writes rules, 
00270                             //and from which they can be read
00271   char subsysFileName[64];  // Name of file to which rkbp saves subsystem info,
00272                             // and from which that can be read
00273   char sysFileName[64];     // Name of file to which rkbp saves system info
00274                             // and from which that can be read
00275 
00276   VectorOf<Chars> generatorNames;
00277   WordOrder order;
00278   VectorOf<int> index; // index[i] gives the integer rkbp uses to label the 
00279    // i-th generator (an integer in the range 
00280    // 0..2*generatorNames.length()-1). index[0] is meaninless.
00281   VectorOf<int> index_inv; // index_inv[i] gives the integer rkbp uses to 
00282   //label the inverse of the i-th generator (an integer in the 
00283   //range 0..2*generatorNames.length()-1). index_inv[0] is meaningless.
00284   VectorOf<int> genNumber; // genNumber[i] gives the number (as returned by the
00285  // Generator function ord)  attached to the generator which rkbp labels with i.
00286   BlackBox theRKBPackage;
00287 
00288 
00289   // Methods:
00290 
00291   void initialize(const VectorOf<Chars>& genNames, const SetOf<Word>& relators,
00292                   const WordOrder & word_order);
00293     // Initialize the process on a specified set of generator names
00294     // and relations, with a specified word order.
00295   void restartProcess();
00296   void haltProcess();
00297   void createSystemFile();
00298   void setWeightsAndLevels(ofstream & rkbp_system);
00299   void createSubsystemFile();
00300   void createRulesFile(const SetOf<Word>& relators);
00301   void skipToNextPrompt();
00302   void skipToImmediatePrompt();
00303   void printWord(ostream& str,const Word& w);
00304   Word readWord(istream& str);
00305   void readSummary();
00306   float* readProbe(int maxLen);
00307   DiffMachine convertToDiffMachine(DiffMachineRep * R)const ;
00308   KBMachine convertToKBMachine(KBMachineRep * R) const;
00309   void buildDifferenceMachine(DiffMachineRep & D, 
00310                          const SetOf<Word> & differences);
00311   void buildKnuthBendixMachine(KBMachineRep & K); 
00312 };
00313 
00314 #endif  

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