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

/magnus/back_end/Group/include/TietzeTrekker.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: TietzeTrekker.h,v 1.1.1.1 1995/11/20 17:54:20 rogern 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 the TietzeTrekker class.
00009 //           A TietzeTrekker is a wrapper for a BlackBox which invokes
00010 //           Frank Rimlinger's TietzeTrek with a group presentation.
00011 //
00012 // Principal Author: Roger Needham
00013 //
00014 // Status: experimental
00015 //
00016 // Revision History:
00017 //
00018 // Next implementation steps:
00019 //
00020 // * TietzeTrek doesn't listen to cin. Make it.
00021 //   - It should respond to a quit command from cin.
00022 //   - The transformation strategy can be tweaked; make commands for that.
00023 //
00024 // * For safety, check for parse error message after reading Frank's
00025 //   presentations.
00026 //
00027 // * The BlackBox may go bad in the middle of the run. This should be
00028 //   detected and reported by sanityCheck(), but still allow calls to
00029 //   knownTo*.
00030 //
00031 // Bugs:
00032 //
00033 // * If a generator in a presentation does not appear in any relator,
00034 //   Frank doesn't know about it. Thus <a,b,c; a=b> is infinite cyclic.
00035 //   Given Frank's flaky API, there is no good workaround. Giving a relator
00036 //   c c^-1 doesn't work, since he freely reduces the input, and I can't
00037 //   find where. Moreover, when a relator reduces to the empty word, it
00038 //   triggers a bug.
00039 //   The present kludge is to give relators like c x c^-1, x. This
00040 //   significantly delays the discovery of very obvious facts, but
00041 //   presumably the caller has already checked for obvious free generators.
00042 //
00043 // * The TietzeTrek is not commanded to exit when a TietzeTrekker is destructed.
00044 //   It seems to go away anyhow (broken pipes), but that's too hacky.
00045 //
00046 // Usage:
00047 // 
00048 // Instantiate a TietzeTrekker on, e.g., a FPGroup G by
00049 // 
00050 //   TietzeTrekker TT( G.namesOfGenerators(), G.getRelators() );
00051 // 
00052 // Make sure that TT.sanityCheck() returns TRUE.
00053 // There is now an asynchronous process associcated with TT which is
00054 // continuously generating presentations, along with statements of
00055 // certain facts (factoids) which can readily be deduced from certain
00056 // presentations.
00057 // Get the `next' presentation from getPresentation().
00058 // To be `notified' of any factoids, first call getFactoid (see comment
00059 // thereon), then call knownTo*. If you don't like the answer, call
00060 // getFactoid again, etc.
00061 
00062 
00063 #ifndef _TIETZE_TREKKER_H_
00064 #define _TIETZE_TREKKER_H_
00065 
00066 
00067 #include "BlackBox.h"
00068 #include "FPGroup.h"
00069 
00070 
00071 class TietzeTrekker {
00072 
00073 public:
00074 
00075   TietzeTrekker(const FPGroup& G);
00076   // Fire up Frank Rimlinger's TietzeTrek with the presentation of G.
00077 
00078   TietzeTrekker(const VectorOf<Chars>& genNames, const SetOf<Word>& relators);
00079   // Fire up Frank Rimlinger's TietzeTrek with the given `presentation'.
00080 
00081   //@rn Need a destructor, which tells TietzeTrek to quit.
00082 
00083   Bool sanityCheck( ) { return ( status == 1 ); }
00084   // Says whether this TietzeTrekker thinks its initialization was successful.
00085 
00086   Bool getFactoid(Bool queuePresentations, long giveUpLimit = 100);
00087   // The first argument says whether to save any presentations
00088   // which are found before the next factoid. Saved ones are later returned
00089   // by getPresentation().
00090   // The second argument specifies the number of lines to read from the
00091   // BlackBox in search of a factoid before giving up and returning.
00092   // The return value says whether a new factoid was discovered.
00093 
00094   // The following indicate what facts have been discovered so far by 0
00095   // or more calls to getFactoid (FALSE means "don't know (yet)"):
00096 
00097   Bool knownToBeTrivial( )      { return (flags & TRIVIAL) != 0; }
00098   Bool knownToBeCyclic( )       { return (flags & CYCLIC) != 0; }
00099   Bool knownToHaveFreeFactor( ) { return (flags & HAS_FREE_FACTOR) != 0; }
00100   Bool knownToBeFinite( )       { return (flags & FINITE) != 0; }
00101   Bool knownToBeFree( )         { return (flags & FREE) != 0; }
00102 
00103   int getOrder( );
00104   // Returns the order of the group in `standard' format: -1 == DONTKNOW,
00105   // 0 == INFINITE, otherwise actual order. If the answer is -1, you can
00106   // call getFactoid (again) for another throw of the dice.
00107 
00108   int getRank( );
00109   // Returns the rank of the group AFTER knownToBeFree() has returned TRUE.
00110   // It is a fatal error if this is called when !knownToBeFree().
00111 
00112   FPGroup getPresentation( );
00113   // Returns another presentation of the finitely presented group
00114   // (representation) used to instantiate this TietzeTrekker, in the form
00115   // of a FPGroup.
00116 
00117 
00118 private:
00119 
00120   enum { TRIVIAL = 1, CYCLIC = 2, HAS_FREE_FACTOR = 4, FINITE = 8, FREE = 16 };
00121 
00122   // Data members;
00123 
00124   ListOf<FPGroup> presentations;
00125   // Presentations queued by getFactoid.
00126 
00127   BlackBox TietzeTrek;  // The BlackBox we're wrapping.
00128 
00129   int flags;            // Flag what we know with values from above enum.
00130   int order;            // Store order if we know it.
00131   int rank;             // Store free rank if we know it.
00132 
00133   int status;           // Initialization status: 1 == good, 0 == bad.
00134 
00135 
00136   // Private methods:
00137 
00138   void initialize(const VectorOf<Chars>& genNames, const SetOf<Word>& relators);
00139   // Does the actual work of construction.
00140 
00141   void printWord(ostream& ostr, const Word& w);
00142   // A special word printer, to work around the ineptitudes in Frank's API.
00143 
00144   void printGenerator(ostream& ostr, int g);
00145   // Prints g as [a-zA-Z].
00146 };
00147 
00148 #endif

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