/* file rws.h * 6/2/98 - large scale re-organisation * 9.1.98. change `char' to `gen' for generator type. * 1.4.95. components rkminlen, rkmineqns added * 6/10/94.
*/
#ifndef KBMAG_RWS_H #define KBMAG_RWS_H
#include <sys/times.h>
#include"fsa.h"
typedefenum {
SHORTLEX,
RECURSIVE,
RT_RECURSIVE,
WTLEX,
WREATHPROD,
NONE
} kbm_orderings; /* Default ordering is SHORTLEX, the other is RECURSIVE path ordering. * WTLEX is where the generators have weights, and the length i * determined by adding up the weights of the generators in the strings. * (so SHORTLEX is WTLEX with all weights 1). * WREATHPROD is as defined in Sims' book, where generators have levels. * Note RECURSIVE is a special case of this, where levels are 1,2,3,... * NONE means order equations as they arrive - not very useful ? * If more orderings are required, add more constants here and alter * the compare routine.
*/
typedefstruct {
gen *lhs; /* left hand side of equation stored as string */
gen *rhs; /* right hand side of equation stored as string */
boolean done; /* true if equation has been handled on a earlier run */
boolean changed; /* true if changed during tidying up */
boolean eliminated; /* true if eliminated during tidying up */
} reduction_equation;
typedefstruct { char name[256]; /* name of system for printing */
kbm_orderings ordering; /* ordering used on strings */ int *weight; /* for wtlex ordering */ int *level; /* for wreathprod ordering */
boolean confluent; /* true if system has been proved confluent */ int num_gens; int num_eqns; int num_inveqns; /* number of equations at beginning of list
* of length 2 and form g*inv_of[g] = 1 */ int *inv_of; /* list of inverse numbers of generators */ char **gen_name; /* names of generators for printing */
reduction_equation *eqns; /* list of equations */
fsa *reduction_fsa; /* finite state automaton for word reduction */ int num_states;
boolean worddiffs; /* true if computing word-differences */
fsa *wd_fsa; /* word-difference machine */
boolean cosets; /* true if doing a cosets calculation */
boolean wd_reorder; /* reorder equations to promote those that * gave rise to new word-diffs -
* should be true */
boolean *new_wd; /* for recording which equations gave
* rise to new word-diffs */ int maxlenleft; /* max stored length of lhs of equation */ int maxlenright; /* max stored length of rhs of equation */ int maxoverlaplen; /* max overlap length processed */
boolean hadlongoverlap; int rkminlen; /* min length for Rabin-Karp word reduction */ int rkmineqns; /* min no of eqns for Rabin-Karp reduction */
boolean rk_on; /* start using Rabin-Karp */ int *history; /* state history on reduction */ int **slowhistory; int *slowhistorysp; /* for use in slow-reduction */ int *preflen; int *prefno; /* for recording prefixes of left-hand-sides
* when building reduction fsa. */ int maxpreflen; /* max. length of prefix */
boolean outputprefixes; /* output names of states of reduction fsa */
gen *testword1;
gen *testword2; /* for storing words during reduction */
boolean sorteqns; /* true if equations are to be sorted
* by length before output. */ int tidyint; /* tidying up interval */ int *eqn_no; /* eqn_no[i]=j means the i-th equation read in becomes * equation number j. (usually i=j) - needed only if the * "done" values are read in.
*/ int nneweqns; int tot_eqns; /* like rws.num_eqns, but not decreased if we
* throw equations away when maxeqns exceeded. */ int hadct; int maxhad; int maxoplen; /* max length of equations output -
* only used if sorteqns is true */
boolean print_eqns; /* print equations as they are generated */ int maxeqns; /* maximum number of equations */
boolean hadmaxeqns; /* true when max. exceeded */ int confnum; /* number of tests before fast confluence */ int oldconfnum; /* number of tests before fast confluence */ int maxslowhistoryspace; int maxreducelen; /* max. length allowed when reducing */ int maxstates; /* maximum number of states in red. machine */ int current_maxstates; /* maximum number of states in red. machine */
boolean double_states; /* do when current_maxstates exceeded */ int init_fsaspace; /* initial table space in red. machine */ int maxwdiffs; int exit_status; /* code for returning on exit */
boolean tidyon; /* set when time to tidy */
boolean tidyon_now; /* set when time to tidy immediately */ /* The following items are used to record progress of calculation, * and for trying to decide when to stop - this is a difficult problem! * They are only used when we are calculating word-differences.
*/ struct wdr { int num_eqns; int num_states; int num_diff;
} * wd_record; /* one entry for each calculation of word-differences, after
* tidying */
int num_cycles; /* number of times we have been through the
* tidying loop */ int eqn_factor; /* Percentage by which number of equations has increased since * number of word-differences increased. No sense in
* halting unless > 0. */ int states_factor; /* Percentage by which number of states has increased
* since number of word-differences increased. */ int halting_factor; int min_time;
boolean halting; /* true when time to halt */
boolean do_conf_test;
boolean lostinfo; /* true when definign relations thrown away */
boolean resume; /* true when re-running */
boolean resume_with_orig; /* true when re-running + original equations */ /* the next ones are set true when set in command-line, since * this overrides settings in the input file.
*/
boolean tidyintset;
boolean maxeqnsset;
boolean maxstatesset;
boolean orderingset;
boolean silentset;
boolean verboseset;
boolean confnumset;
boolean maxreducelenset;
boolean maxwdiffset; /* The final few are needed only when cosets is true */ int separator; /* assumed to be generator with name "_H" */ int maxlhsrellen; int maxsubgenlen; int maxcosetlen;
boolean finitestop;
boolean Hoverlaps;
boolean Gislevel; /* true if all gens. of G have same level */
boolean Hislevel; /* true if all gens. of H have same level */
boolean Hhasinverses; /* true if all H-gens have inverses */
srec *wd_alphabet;
gen **subwordsG;
} rewriting_system;
/* The reduction_struct is just a typedef for the second parameter of * the word_reduce function, which is sometimes a rewriting system and * sometimes a word-difference fsa + separator symbol.
*/ typedefstruct {
rewriting_system *rws;
fsa *wd_fsa; int separator; /* the last three are just for weight-lex reduction */
fsa *wa; int *weight; int maxreducelen;
} reduction_struct;
void build_quicktable(rewriting_system *rwsptr); int modify_table(int relno, rewriting_system *rwsptr); int insert(gen **lhs, gen **rhs, rewriting_system *rwsptr);
/* rabkar.c */ int rk_init(rewriting_system *rwsptr); void rk_reset(int maxeqns); void rk_clear(rewriting_system *rwsptr); void rk_add_lhs(int n, rewriting_system *rwsptr); int slow_rws_reduce_rk(gen *w, reduction_struct *rs_rws);
boolean slow_check_rws_reduce_rk(gen *w, int i, rewriting_system *rwsptr);
/* rwsreduce.c */ void rws_clear(rewriting_system *rwsptr); int rws_reduce(gen *w, reduction_struct *rs_rws); int slow_rws_reduce(gen *w, reduction_struct *rs_rws);
boolean slow_check_rws_reduce(gen *w, int i, rewriting_system *rwsptr);
#endif
Messung V0.5
¤ Dauer der Verarbeitung: 0.12 Sekunden
(vorverarbeitet)
¤
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
