#############################################################################
##
#A rws4.g GAP library Derek Holt
##
## This file contains those functions that deal with rewriting systems.
##
## 1.3.00. created this file from GAP3 version rws.g and started adapting
## it to GAP4.
##
## 1.8.96.
## Changed the ReorderGenerators command to permute the alphabet
## themselves, and deleted the generatorOrder field. This avoids the
## need of permuting columns of fsa's when updating.
##
## 15.3.95.
## Each (internal) rewriting-system now has components "GpMonSgp" (for the
## associated group or monoid), "generators" (for the generators, which
## will include those of GpMonSgp, but may also include inverses
## in the group case), and "namesGenerators", which again include
## those of GpMonSgp, but will have names with "^-1" adjoined for inverses.
##
## When an externally created file containing a rewriting-system is read in
## to GAP, a preprocessing external program called "ppgap" is run, which
## creates a file called "file.gap", which includes necessary declarations
## of a suitable underlying monoid.
##
## 23.2.95. The internal storage of a rewriting system was changed so
## that generators are simply numbers in the range [1..ng] for some ng,
## and words are lists of generator numbers.
##
DeclareInfoClass("InfoRWS");
#############################################################################
#V _RWS external variable - the name of the rewriting system
#V _RWS_Sub external variable - subgroup of the rewriting system
#V _RWS_Cos external variable - coset rewriting system
#V _RWS.GpMonSgp external variable - name of underlying group or monoid
#V _RWS.FreeGpMonSgp external variable - name of underlying group or monoid
#V _KBExtDir external variable - directory of external executables
#V _KBTmpFileName external variable - name of temporary file.
#V _ExitCode external variable - exit code of programs.
##
_RWS := rec();
_RWS_Sub := rec();
_RWS_Cos := rec();
_ExitCode := 0;
#############################################################################
##
#F IsConfluentRWS(<x>) . . . . . . . test whether x is a confluent rws
##
## Public function.
IsConfluentRWS := function ( x )
if not IsKBMAGRewritingSystemRep(x) then return false; fi;
if not IsBound(x!.isConfluent) then return false; fi;
return x!.isConfluent;
end;
#############################################################################
##
#F IsGroupRWS(<rws>) . . . test whether all gens of rws <rws> have inverses
##
## Public function.
IsGroupRWS := function ( rws )
local gp, g;
if not IsKBMAGRewritingSystemRep(rws) then return false; fi;
gp:=true;
for g in rws!.invAlphabet do
if g = false then gp:=false; fi;
od;
return gp;
end;
#############################################################################
##
#F IsMonoidRWS(<rws>) . . . does <rws> represent a monid
##
## This merely returns the value of rws!.hasOne.
## Note that if this is false, then there should be no inverses!
## Public function.
IsMonoidRWS := function ( rws )
if not IsKBMAGRewritingSystemRep(rws) then return false; fi;
return rws!.hasOne;
end;
#############################################################################
##
#F LinePrintRWS(<line> [,<filename>]) . . . . . . . print the line x
##
## LinePrintRWS prints the line (a string) to the terminal (default)
## or to file filename if specified, formatting nicely.
## It works by building up the material to be printed line by line as strings,
## and calling LinePrintRWS to print each individual line.
LinePrintRWS := function ( arg )
local line, filename;
line := arg[1];
if Length(arg) = 1 then
filename := "";
else
filename := arg[2];
fi;
if filename = "" then
Print(line,"\n");
else
AppendTo(filename,line,"\n");
fi;
end;
#############################################################################
##
#F FpStructureRWS(<rws>) . finitely presented group or semigroup defining <rws>
##
## Public function.
FpStructureRWS := function ( rws )
local F, M, IdWord, rels, gens, ng, i, ig, eqn, w1, w2;
if not IsKBMAGRewritingSystemRep(rws) then
Error("Argument is not an KBMAG rewriting system.");
fi;
if IsBound(rws!.GpMonSgp) then
return rws!.GpMonSgp;
fi;
## We have to calculate it!
M := rws!.WordMonoid;
IdWord := One(M);
rels := Set([]);
gens := rws!.alphabet;
ng := Length(rws!.alphabet);
for i in [1..ng] do
ig := rws!.invAlphabet[i];
if ig <> false then
AddSet(rels,[gens[i]*gens[ig],IdWord]);
AddSet(rels,[gens[ig]*gens[i],IdWord]);
fi;
od;
for eqn in rws!.equations do
w1 := ListToWordRWS(eqn[1],gens);
w2 := ListToWordRWS(eqn[2],gens);
if w1<>w2 then AddSet(rels,[w1,w2]); fi;
od;
#Now convert to external representation.
F := rws!.FreeGpMonSgp;
rels := List(rels,r -> [rws!.IntToExt(rws!.ExtIntCorr,r[1]),
rws!.IntToExt(rws!.ExtIntCorr,r[2])] );
if IsGroup(F) then
rels := List(rels,r -> r[1]/r[2] );
fi;
rws!.GpMonSgp := F/rels;
return rws!.GpMonSgp;
end;
#############################################################################
##
#F IsAvailableNormalFormRWS(<x>) . . . . test whether x has a normal form
##
## Public function.
IsAvailableNormalFormRWS := function ( x )
return IsKBMAGRewritingSystemRep(x) and
IsBound(x!.isAvailableNormalForm) and
x!.isAvailableNormalForm=true;
end;
#############################################################################
##
#F IsAvailableReductionRWS(<x>) . . test whether x has a reduction algorithm
##
## Public function.
IsAvailableReductionRWS := function ( x )
return IsKBMAGRewritingSystemRep(x) and
IsBound(x!.isAvailableReduction)
and x!.isAvailableReduction=true;
end;
#############################################################################
##
#F IsAvailableSizeRWS(<x>) . . test whether x has a size algorithm
##
## Public function.
IsAvailableSizeRWS := function ( x )
return IsKBMAGRewritingSystemRep(x) and
IsBound(x!.isAvailableSize)
and x!.isAvailableSize=true;
end;
#############################################################################
##
#F ResetRWS(<rws>) . . . . . . . . . . . reset rws after a call of KBRUN.
##
## Public function.
## This resets a rewriting system back to the original equations, after a
## call of KBRUN or AutRWS.
ResetRWS := function ( rws )
if not IsKBMAGRewritingSystemRep(rws) then
Error("First argument is not a rewriting system.");
fi;
Unbind(rws!.KBRun);
Unbind(rws!.isConfluent);
Unbind(rws!.isAvailableNormalForm);
Unbind(rws!.isAvailableReduction);
Unbind(rws!.isAvailableSize);
Unbind(rws!.warningOn);
Unbind(rws!.reductionFSA);
Unbind(rws!.wa);
Unbind(rws!.diff1);
Unbind(rws!.diff1c);
Unbind(rws!.diff2);
Unbind(rws!.gm);
if IsBound(rws!.originalEquations) then
Unbind(rws!.equations);
rws!.equations := rws!.originalEquations;
Unbind(rws!.originalEquations);
fi;
end;
#############################################################################
##
#F NumberSubgroupRWS(<rws>, <subrws>) . . . number of a subgroup of an <rws>
##
## <rws> should be a rewriting system and <subrws> a subgroup.
## The number of the subgroup is returned, or fail if it is not a subgroup.
## (Should be in rwssub4.g really but needed by next function.)
NumberSubgroupRWS := function(rws, subrws)
local i;
if not IsGroupRWS(rws) then
Error("NumberSubgroupRWS only applies to rewriting systems from groups.");
fi;
if not IsKBMAGRewritingSystemRep(subrws) or
not IsBound(subrws!.alphabet) then
Error(
"Second argument of NumberSubgroupRWS must be have generators.");
fi;
if not IsBound(rws!.subgroups)
then return fail;
fi;
for i in [1..rws!.numSubgroups] do
if rws!.subgroups[i]!.alphabet = subrws!.alphabet then
return i;
fi;
od;
return fail;
end;
#############################################################################
##
#F SetOrderingRWS(<rws>,<ord>[,list])
## . . . specify the ordering of a rewriting system
##
## <rws> should be a rewriting system, and <ord> one of the strings that
## defines an ordering on the words in the alphabet of <rws>.
## These are "shortlex", "recursive", rt_recursive", "wtlex" and "wreathprod".
## In the case of "wtlex" and "wreathprod", the extra parameter <list> is
## required, and it should be a list of ng (= number of alphabet of <rws>)
## non-negative integers, specifying the weights or the levels of the
## alphabet, respectively, for this ordering.
## Public function.
SetOrderingRWS := function ( arg )
local rws, ord, list, ng, go, i;
if Length(arg)<2 or Length(arg)>3 then
Error("SetOrderingRWS has 2 or 3 arguments");
fi;
rws:=arg[1];
ord:=arg[2];
if Length(arg)=3 then
list:=arg[3];
else
list:=[];
fi;
if not IsKBMAGRewritingSystemRep(rws) then
Error("First argument is not an KBMAG rewriting system.");
fi;
if not IsString(ord) then
Error("Second argument is not a string.");
fi;
ng := Length(rws!.alphabet);
if Length(arg)=3 then
if not IsList(list) or Length(list)<>ng then
Error("Third argument is not a list of length <ng>.");
fi;
for i in [1..ng] do
if not IsInt(list[i]) or list[i]<0 then
Error("Third argument is not a list of non-negative integers.");
fi;
od;
fi;
if ord="shortlex" or ord="recursive" or ord="rt_recursive" or
ord="wtlex" or ord="wreathprod" then
rws!.ordering:=ord;
else
Error("Unknown ordering",ord);
fi;
if (ord="wtlex" or ord="wreathprod") and list=[] then
Error("Third argument required for ordering",ord);
fi;
if ord="wtlex" then rws!.weight:=list; fi;
if ord="wreathprod" then rws!.level:=list; fi;
end;
#############################################################################
##
#F ReorderGeneratorsRWS(<rws>,<p>) . reorder alphabet of a rewriting system
##
## <rws> should be a rewriting system, and <p> a permutation of the set
## [1..ng], where <rws> has <ng> = length of alphabet.
## The alphabet of <rws> is reordered by applying the permutation <p> to
## its existing order.
## Public function.
ReorderGeneratorsRWS := function ( rws, p )
local ng, list, i, eqn;
if not IsKBMAGRewritingSystemRep(rws) then
Error("First argument is not an KBMAG rewriting system.");
fi;
if not IsPerm(p) then
Error("Second argument is not a permutation.");
fi;
ng := Length(rws!.alphabet);
if LargestMovedPointPerm(p) > ng then
Error("Permutation is on more points than there are alphabet!");
fi;
list:=[];
for i in [1..ng] do list[i^p]:=rws!.alphabet[i]; od;
rws!.alphabet:=list;
list:=[];
for i in [1..ng] do
if IsInt(rws!.invAlphabet[i]) then
list[i^p]:=rws!.invAlphabet[i]^p;
else list[i^p] := false;
fi;
od;
rws!.invAlphabet:=list;
for eqn in rws!.equations do
list := List(eqn[1],i->i^p);
eqn[1]:=list;
list := List(eqn[2],i->i^p);
eqn[2]:=list;
od;
if IsBound(rws!.originalEquations) then
for eqn in rws!.originalEquations do
list := List(eqn[1],i->i^p);
eqn[1]:=list;
list := List(eqn[2],i->i^p);
eqn[2]:=list;
od;
fi;
if IsBound(rws!.weight) then
list:=[];
for i in [1..ng] do list[i^p]:=rws!.weight[i]; od;
rws!.weight:=list;
fi;
if IsBound(rws!.level) then
list:=[];
for i in [1..ng] do list[i^p]:=rws!.level[i]; od;
rws!.level:=list;
fi;
end;
#############################################################################
##
#F ReadRWS(<filename>, [semigp]) . . . .read and convert a rewriting system
##
## ReadRWS reads a rewriting system, which must be declared with the
## external variable name "_RWS" from the file <filename>, and converts it
## to internal format. First it creates and reads the GAP preprocessor file
## <filename>.gap, for the declarations of variable names.
## This is created using the external program "ppgap".
## The rewriting system is returned.
## If the optional second argument is true, then the rewriting system is
## regarded as being for a semigroup rather than for a monoid (default).
## This means that the empty word is not part of the language.
## For this to be the case there must be no inverses, or an error will result.
## Public function.
ReadRWS := function ( arg )
local i, rgm, rfgm, rws, ng, p, ig, ri,
eqn, filename, semigp, mnames, fam, isgp, l, s, gtom, igtom;
filename:=arg[1];
if Length(arg)>1 then
semigp := arg[2];
else
semigp := false;
fi;
Exec(Concatenation(Filename(_KBExtDir,"ppgap4")," ",filename));
Read(Concatenation(filename,".gap4"));
Exec(Concatenation("/bin/rm -f ",filename,".gap4"));
rfgm := _RWS.FreeGpMonSgp;
#This is about to get overwritten, so we remember it!
if not READ(filename) then Error("Could not open file for reading"); fi;
rws := _RWS; _RWS := rec(); #reset _RWS for next time
rws.FreeGpMonSgp := rfgm;
isgp := IsGroup(rfgm);
rws.hasOne := not semigp;
rws.options := rec();
#Several of the fields of the rewriting system are stored differently
#or have different names in the internal storage, than the way they
#appear in the file.
ng := Length(rws.generatorOrder);
#Internally, inverses are not stored as a list of alphabet, but as
#a list of integers (in the field invAlphabet), giving the position
#of the inverse generator in the generator list.
ri := rws.inverses;
ig := []; rws.invAlphabet := ig;
for i in [1..ng] do
if IsBound(ri[i]) then
ig[i] := Position(rws.generatorOrder,ri[i]);
if semigp then
Error("There can be no inverse in a semigroup.");
fi;
else
ig[i] := false;
fi;
od;
Unbind(rws.inverses);
#The left- and right-hand sides of the equations are not stored
#internally as words, but as lists of integers, giving the numbers of
#the alphabet appearing in the list.
for eqn in rws.equations do
eqn[1] := WordToListRWS(eqn[1],rws.generatorOrder);
eqn[2] := WordToListRWS(eqn[2],rws.generatorOrder);
od;
mnames := [];
for i in [1..ng] do
if isgp then mnames[i] := Concatenation("_g",String(i));
else mnames[i] := Concatenation("_m",String(i));
fi;
od;
rws.WordMonoid := FreeMonoid(mnames);
rws.alphabet := GeneratorsOfMonoid(rws.WordMonoid);
#Now we have to set up the Ext/Int correspondence.
#This is tricky for groups, because some of the names in the
#external file might have form "x^-1".
if isgp then
gtom := []; igtom :=[];
for i in [1..ng] do
s:=String(rws.generatorOrder[i]);
l:=Length(s);
if l<=3 or s{[l-2..l]} <> "^-1" then
Add(gtom,i);
Add(igtom,rws.invAlphabet[i]);
fi;
od;
rws.ExtIntCorr :=
CorrespondenceGroupMonoid(rfgm,rws.WordMonoid,gtom,igtom);
rws.ExtToInt := FreeGroup2FreeMonoid;
rws.IntToExt := FreeMonoid2FreeGroup;
else
rws.ExtIntCorr :=
CorrespondenceGroupMonoid(rfgm,rws.WordMonoid);
rws.ExtToInt := FreeMS2FreeMonoid;
rws.IntToExt := FreeMonoid2FreeMS;
fi;
Unbind(rws.generatorOrder); #we no longer use this field.
fam := NewFamily("Family of Knuth-Bendix Rewriting systems",
IsKnuthBendixRewritingSystem);
rws := Objectify(NewType(fam,
IsMutable and IsKnuthBendixRewritingSystem
and IsKBMAGRewritingSystemRep),
rws);
FpStructureRWS(rws);
return rws;
end;
#############################################################################
##
#F ExtVarHandlerRWS(<rws>, <filename>) . . write file to handle externals
##
## This is hopefully a temporary hack, for use until GAP V4, where should be
## a better solution. A GAP file is written to preserve any existing values
## of external variables corresponding to the generator names of the
## rewriting system <rws>, and then to declare these variables to be equal
## to the corresponding alphabet of <rws>. This is necessary for reading
## back in the output of KBRWS or AutRWS, which uses these names.
## This first file is called <rws>.gap1.
## A second file <rws>.gap2 is written for reading afterwards, which restores
## the values of any previously existing externals with those names.
## The files are read by the following two functions below.
##
ExtVarHandlerRWS := function(rws, filename)
local file1, file2, ng, names, line, i, ni, l;
file1 := Concatenation(filename,".gap1");
file2 := Concatenation(filename,".gap2");
PrintTo(file1,"_RWS.oldNames:=false;\n");
PrintTo(file2,"");
ng := Length(rws!.alphabet);
names := List(rws!.alphabet,x->String(x));
_RWS.WordMonoid := rws!.WordMonoid;
for i in [1..ng] do _RWS.(i) := rws!.alphabet[i]; od;
for i in [1..ng] do
ni := names[i]; l := Length(ni);
if l <= 3 or ni{[l-2..l]} <> "^-1" then
line := Concatenation("if IsBound(",ni,") and ",ni,
" <> _RWS.WordMonoid.",String(i)," then _RWS.",String(i+ng),":=",
ni,"; _RWS.oldNames:=true; fi;\n");
line := Concatenation(line,ni,":=_RWS.WordMonoid.",String(i),";\n");
AppendTo(file1,line);
line := Concatenation("if IsBound(_RWS.",String(i+ng),") then ",
ni,":=_RWS.",String(i+ng),"; fi;\n");
AppendTo(file2,line);
fi;
od;
line := Concatenation(
"if IsBound(_) and _ <> One(_RWS.WordMonoid) then _RWS.",
String(2*ng+1), ":=_;\n _RWS.oldNames:=true; fi;\n");
line := Concatenation(line,"_:=One(_RWS.WordMonoid);\n");
AppendTo(file1,line);
line := Concatenation("if IsBound(_RWS.",String(2*ng+1),
") then _:=_RWS.",String(2*ng+1),"; fi;\n");
AppendTo(file2,line);
line := Concatenation(
"if IsBound(IdWord) and IdWord <> One(_RWS.WordMonoid) then _RWS.",
String(2*ng+2), ":=IdWord;\n _RWS.oldNames:=true; fi;\n");
line := Concatenation(line,"IdWord:=One(_RWS.WordMonoid);\n");
AppendTo(file1,line);
line := Concatenation("if IsBound(_RWS.",String(2*ng+2),
") then IdWord:=_RWS.",String(2*ng+2),"; fi;\n");
AppendTo(file2,line);
end;
#############################################################################
##
#F StoreNamesRWS(<rws>, <filename>)
## Store existing variables before reading external file.
StoreNamesRWS := function(rws, filename)
local i;
ExtVarHandlerRWS(rws,filename);
Read(Concatenation(filename,".gap1"));
rws!.oldNames := _RWS.oldNames;
end;
#############################################################################
##
#F RedefineNamesRWS(<rws>, <filename>)
## Redefine existing variables after reading external file.
## Store existing variables.
RedefineNamesRWS := function(rws, filename)
local i;
if rws!.oldNames then
Read(Concatenation(filename,".gap2"));
fi;
_RWS := rec();
_RWS_Cos := rec();
end;
#############################################################################
##
#F UpdateRWS(<rws>, <filename>, <kb>, [<cosets>])
## . . update rws, after run of external program
##
## This function is called after a run of one of the "documented" external
## programs (currently KBRWS and AutRWS) on the rewriting system <rws>.
## It updates <rws> being careful to reset any external variables that were
## used by the external program, but previously existed in the current GAP
## session. <filename> should be the file in which the
## original rewriting-system was stored. <kb> should be true or false,
## according to whether the function is being called from a Knuth-Bendix
## application (KBRWS) or automatic groups (AutRWS).
## In the Knuth-Bendix case, <filename>.kbprog is read in, for the updated
## version of the equations. Then <filename>.reduce is read in
## for the reduction machine.
## In the automatic groups case, <filename>.wa is read in for the word-acceptor,
## and then <filename.diff2> and <filename>.diff1c for the word-difference
## machines used in word reduction.
##
UpdateRWS := function(arg)
local rws, filename, kb, cosets, _RWSrec, x, i, j, k, l, eqn, twovar,
fsa, fsa2, fsa3, newrow, ig, mg, alph, la, efilename;
rws := arg[1];
filename := arg[2];
kb := arg[3];
cosets := false;
if Length(arg)>=4 then
cosets := arg[4];
fi;
#Make preprocessing file
StoreNamesRWS(rws, filename);
if cosets then
_RWS_Cos := _RWS;
fi;
mg := GeneratorsOfMonoid(rws!.WordMonoid);
if cosets then
alph := rws!.baseAlphabet;
else
alph := rws!.alphabet;
fi;
la := Length(alph);
if kb then
#Read in updated version of equations.
if not READ(Concatenation(filename,".kbprog")) then
Error("Could not open output of external Knuth-Bendix program.");
fi;
if cosets then _RWSrec := _RWS_Cos; else _RWSrec := _RWS; fi;
rws!.equations := _RWSrec.equations;
for eqn in rws!.equations do
eqn[1] := WordToListRWS(eqn[1],mg);
eqn[2] := WordToListRWS(eqn[2],mg);
od;
rws!.isConfluent := _RWSrec.isConfluent;
if cosets then
rws!.ordering := _RWSrec.ordering;
rws!.level := _RWSrec.level;
fi;
fi;
# read automata
if kb then
if not READ(Concatenation(filename,".reduce")) then
Error("Could not open reduction machine file");
fi;
fsa:= _RWSrec.reductionFSA;
rws!.reductionFSA := fsa;
if not rws!.hasOne then # empty word should not be accepted.
fsa.accepting := [2..fsa.states.size];
fi;
for i in [1..la] do
fsa.alphabet.names[i] := alph[i];
#They may got re-ordered!
od;
else
if cosets then _RWSrec := _RWS_Cos; else _RWSrec := _RWS; fi;
if not READ(Concatenation(filename,".wa")) then
Error("Could not open word-acceptor file");
fi;
fsa := _RWSrec.wa;
rws!.wa := fsa;
for i in [1..la] do
fsa.alphabet.names[i] := alph[i];
#They may got re-ordered!
od;
if cosets then efilename:=Concatenation(filename,".midiff1");
else efilename:=Concatenation(filename,".diff1c");
fi;
if not READ(efilename) then
Error("Could not open word-difference file");
fi;
if cosets then fsa2 := _RWS.midiff1; else fsa2 := _RWS.diff1c; fi;
if cosets then rws!.midiff1 := fsa2; else rws!.diff1 := fsa2; fi;
if cosets then efilename:=Concatenation(filename,".midiff2");
else efilename:=Concatenation(filename,".diff2");
fi;
if not READ(efilename) then
Error("Could not open word-difference file");
fi;
if cosets then fsa3 := _RWS.midiff2; else fsa3 := _RWS.diff2; fi;
if cosets then rws!.midiff2 := fsa3; else rws!.diff2:=fsa3; fi;
#fsa2.alphabet.type := "simple";
#fsa3.alphabet.type := "simple";
for i in [1..la] do
fsa2.states.alphabet[i] := alph[i];
fsa3.states.alphabet[i] := alph[i];
#They may got re-ordered!
od;
fi;
#Reset any lost existing externals
RedefineNamesRWS(rws, filename);
InitializeFSA(fsa);
#Make sure the table is stored densely
DenseDTableFSA(fsa);
fsa.table.format:="dense deterministic";
fsa.table.transitions:=fsa.denseDTable;
Unbind(fsa.sparseTable);
fsa.alphabet.printingStrings:=List(rws!.alphabet,x->String(x));
if not kb then
InitializeFSA(fsa2);
InitializeFSA(fsa3);
#Make sure the table is stored densely
DenseDTableFSA(fsa2);
DenseDTableFSA(fsa3);
#fsa2.alphabet.base.printingStrings:=List(rws!.alphabet,x->String(x));
#fsa3.alphabet.base.printingStrings:=List(rws!.alphabet,x->String(x));
fsa2.states.printingStrings:=List(rws!.alphabet,x->String(x));
fsa3.states.printingStrings:=List(rws!.alphabet,x->String(x));
fsa2.table.format:="dense deterministic";
fsa3.table.format:="dense deterministic";
fsa2.table.transitions:=fsa.denseDTable;
fsa3.table.transitions:=fsa.denseDTable;
Unbind(fsa2.sparseTable);
Unbind(fsa3.sparseTable);
fi;
end;
#############################################################################
##
#F WriteRWS(<rws>, [<filename>], [<endsymbol>])
## . . . . . . . . . . . .write an rws to a file in external format
##
## WriteRWS prints the rws <rws> to the file <filename> formatting nicely.
## It works by building up the material to be printed line by line as strings,
## and calling LinePrintRWS to print each individual line.
## If <filename> is not present, or empty, then writing is to the terminal
## and is simply of form rec(..).
## Otherwise, printing takes form _RWS := rec(...)<endsymbol>
## where <endsymbol> is a string which is ";" by default.
## (_RWS is a global variable.)
##
## Public function.
WriteRWS := function ( arg )
local rws, name, filename, gapfilename, line, i, eqn, endsymbol,
ng, en, gn, ls, ig;
if Length(arg)<1 then
Error("WriteRWS has 1, 2 or 3 arguments");
fi;
rws := arg[1];
filename := "";
if Length(arg)>=2 then filename := arg[2]; fi;
if filename="" then endsymbol := ""; else endsymbol := ";"; fi;
if Length(arg)>=3 then endsymbol := arg[3]; fi;
if not IsKBMAGRewritingSystemRep(rws) then
Error("First argument is not an KBMAG rewriting system.");
fi;
ng := Length(rws!.alphabet);
en := List(rws!.alphabet,x->String(x));
#Now print main file
if filename="" then Print("rec(\n");
else PrintTo(filename,"_RWS := rec (\n");
fi;
line := String("isRWS",16);
line := Concatenation(line," := true,");
LinePrintRWS(line,filename);
if IsBound(rws!.isConfluent) then
line := String("isConfluent",16);
line := Concatenation(line," := ",String(rws!.isConfluent),",");
LinePrintRWS(line,filename);
fi;
#Now come all of the optional parameters
if IsBound(rws!.options.tidyint) then
line := String("tidyint",16);
line := Concatenation(line," := ",String(rws!.options.tidyint),",");
LinePrintRWS(line,filename);
fi;
if IsBound(rws!.options.maxeqns) then
line := String("maxeqns",16);
line := Concatenation(line," := ",String(rws!.options.maxeqns),",");
LinePrintRWS(line,filename);
fi;
if IsBound(rws!.options.maxstates) then
line := String("maxstates",16);
line := Concatenation(line," := ",String(rws!.options.maxstates),",");
LinePrintRWS(line,filename);
fi;
if IsBound(rws!.options.maxreducelen) then
line := String("maxreducelen",16);
line := Concatenation(line," := ",String(rws!.options.maxreducelen),",");
LinePrintRWS(line,filename);
fi;
if IsBound(rws!.options.confnum) then
line := String("confnum",16);
line := Concatenation(line," := ",String(rws!.options.confnum),",");
LinePrintRWS(line,filename);
fi;
if IsBound(rws!.options.maxwdiffs) then
line := String("maxwdiffs",16);
line := Concatenation(line," := ",String(rws!.options.maxwdiffs),",");
LinePrintRWS(line,filename);
fi;
if IsBound(rws!.options.maxstoredlen) then
line := String("maxstoredlen",16);
line := Concatenation(line, " := [",
String(rws!.options.maxstoredlen[1]),",",
String(rws!.options.maxstoredlen[2]),"],");
LinePrintRWS(line,filename);
fi;
if IsBound(rws!.options.sorteqns) then
line := String("sorteqns",16);
line := Concatenation(line," := ",String(rws!.options.sorteqns),",");
LinePrintRWS(line,filename);
fi;
if IsBound(rws!.options.maxoplen) then
line := String("maxoplen",16);
line := Concatenation(line," := ",String(rws!.options.maxoplen),",");
LinePrintRWS(line,filename);
fi;
if InfoLevel(InfoRWS)=0 then
line := String("silent",16);
line := Concatenation(line," := true,");
LinePrintRWS(line,filename);
fi;
if InfoLevel(InfoRWS)>1 then
line := String("verbose",16);
line := Concatenation(line," := true,");
LinePrintRWS(line,filename);
fi;
if InfoLevel(InfoRWS)>2 then
line := String("veryVerbose",16);
line := Concatenation(line," := true,");
LinePrintRWS(line,filename);
fi;
line := Concatenation(String("generatorOrder",16)," := [");
for i in [1..ng] do
if i > 1 then
line := Concatenation(line,",");
fi;
if i=1 or Length(line)+Length(en[i]) <= 76 then
line := Concatenation(line,en[i]);
else
LinePrintRWS(line,filename);
line := String("",21);
line := Concatenation(line,en[i]);
fi;
od;
line := Concatenation(line,"],");
LinePrintRWS(line,filename);
ig := rws!.invAlphabet;
line := Concatenation(String("inverses",16)," := [");
for i in [1..ng] do
if i > 1 then line := Concatenation(line,","); fi;
if IsInt(ig[i]) and ig[i]>0 then
if i=1 or Length(line)+Length(en[ig[i]]) <= 76 then
line := Concatenation(line,en[ig[i]]);
else
LinePrintRWS(line,filename);
line := String("",21);
line := Concatenation(line,en[ig[i]]);
fi;
fi;
od;
line := Concatenation(line,"],");
LinePrintRWS(line,filename);
if not IsString(rws!.ordering) then
Error("Can only output orderings that are strings");
fi;
line := String("ordering",16);
line := Concatenation(line," := \"",rws!.ordering,"\",");
LinePrintRWS(line,filename);
if rws!.ordering="wtlex" and IsBound(rws!.weight) then
line := Concatenation(String("weight",16)," := [");
for i in [1..ng] do
if i > 1 then
line := Concatenation(line,",");
fi;
line := Concatenation(line,String(rws!.weight[i]));
od;
line := Concatenation(line,"],");
LinePrintRWS(line,filename);
fi;
if rws!.ordering="wreathprod" and IsBound(rws!.level) then
line := Concatenation(String("level",16)," := [");
for i in [1..ng] do
if i > 1 then
line := Concatenation(line,",");
fi;
line := Concatenation(line,String(rws!.level[i]));
od;
line := Concatenation(line,"],");
LinePrintRWS(line,filename);
fi;
line := Concatenation(String("equations",16)," := [");
for i in [1..Length(rws!.equations)] do
if i > 1 then line := Concatenation(line,","); fi;
LinePrintRWS(line,filename);
eqn := rws!.equations[i];
line := Concatenation(String("[",10),
StringRWS(ListToWordRWS(eqn[1],rws!.alphabet)),",");
if Length(line)>=40 then
LinePrintRWS(line,filename);
line := String("",10);
fi;
line :=Concatenation(line,
StringRWS(ListToWordRWS(eqn[2],rws!.alphabet)),"]");
od;
LinePrintRWS(line,filename);
line := String("]",8);
LinePrintRWS(line,filename);
line := Concatenation(")",endsymbol);
LinePrintRWS(line,filename);
end;
#############################################################################
##
#F IsReducedWordRWS(<rws>,<w>) . . . . tests if a word is reduced
##
## IsReducedWordRWS tests whether the word <w>
## is reduced, using the rewriting system <rws>.
## <w> can be given either as a list of integers (internal format) or as
## a word in the generators of the underlying group or monoid.
## Either the word-acceptor (automatic group case) or the reduction FSA
## must be defined.
## It merely calls the corresponding FSA function.
##
## Public function.
IsReducedWordRWS := function ( rws, w )
local i, ng;
if not IsKBMAGRewritingSystemRep(rws) then
Error("First argument is not an KBMAG rewriting system.");
fi;
if not IsAvailableReductionRWS(rws) then
Error(
"Reduction algorithm unavailable. Run KnuthBendix or AutomaticStructure.");
fi;
if not IsList(w) and not IsWord(w) then
Error("Second argument is not a word or list.");
fi;
ng := Length(rws!.alphabet);
if IsWord(w) then
w:=WordToListRWS(w,rws!.alphabet);
fi;
if IsBound(rws!.wa) then
# Automatic group case - use word-acceptor
return IsAcceptedWordDFA( rws!.wa,w );
fi;
if not IsBound(rws!.reductionFSA) then
Error("First argument does not have initialized dfa as field.");
fi;
return IsAcceptedWordDFA( rws!.reductionFSA,w );
end;
#############################################################################
##
#F ReduceWordWD(<wd>,<w>)
## . . . . .reduces a word using word-difference automaton
##
## ReduceWordWD calculates the reduction of the word <w> (list of integers)
## using the word-difference automaton <wd>.
## <wd> should be two-variable, where <w> is a list of integers in the range
## [1..ng], where ng is the size of the base alphabet.
## WARNING: No validity checks are carried out!
##
## Private function.
ReduceWordWD := function ( wd, w)
local ndiff, ngens, ng1, identity, level, cf, gpref, gct, gptr,
diff, newdiff, deqi, gen1, gen2, donesub, donediffs, subvert,dosub,
g2ltg1, diffct, t, nlen, olen, i, l, table;
if not IsInitializedFSA(wd) then
Error("First argument is not an initialized dfa.");
fi;
ndiff := wd.states.size;
ngens := wd.alphabet.base.size;
ng1 := ngens+1;
identity := wd.initial[1];
if Length(w) <= 0 then
return w;
fi;
cf := [];
# cf is used as a characteristic function, when constructing a subset of the
# set D of word differences.
gpref := []; gct := 0; gpref[1] := 0; gptr := [];
# gpref[n] is the number of "vertices" that have been defined after
# reading the first n-1 elements of the word.
# These vertices are gptr[1],...,gptr[gpref[n]].
# A vertex is a record with 4 components, backptr, genno, diffno, sublen,
# It represents a vertex in the graph of strings that may eventually
# be used as substituted strings in the word w.
# backptr is either undefined or another vertex.
# gen is the generator at the vertex.
# diffno is the word-difference number of the string at which the vertex
# is at the end - this string is reconstructed using backptr.
# sublen is plus or minus the length of this string. sublen is positive
# iff the string lexicographically precedes the corresponding
# prefix of the word being reduced.
# Now we start scanning the word.
table := DenseDTableFSA(wd);
level := 1;
while level <= Length(w) do
for i in [1..ndiff] do cf[i] := false; od;
gen1 := w[level];
# The next loop is over the identity, and the subset of the set of
# word-differences (states of wd) defined at the previous level (level-1)
diff := identity;
donesub := false;
donediffs := false;
while not donesub and not donediffs do
deqi := diff = identity;
# First look for a possible substitution of a shorter string
newdiff := table[diff][ng1*gen1];
if newdiff=identity then
#Make substitution reducing length of word by 1
SubstitutedListFSA(w,level,level,[]);
i := level-1;
if not deqi then
subvert := gptr[diffct];
dosub := true;
while dosub do
w[i] := subvert.gen;
i := i-1;
if IsBound(subvert.backptr) then
subvert := subvert.backptr;
else
dosub := false;
fi;
od;
fi;
#Whenever we make a substitution, we have to go back one level more
#than expected, because of our policy of looking ahead for
#substitutions that reduce the length by 2.
if i>0 then level:=i-1; else level:=i; fi;
gct := gpref[level+1];
donesub := true;
elif newdiff>0 and level<Length(w) then
#See if there is a substitution reducing length by 2.
gen2 := w[level+1];
t := table[newdiff][ng1*gen2];
if t=identity then
#Make substitution reducing length of word by 2
SubstitutedListFSA(w,level,level+1,[]);
i := level-1;
if not deqi then
subvert := gptr[diffct];
dosub := true;
while dosub do
w[i] := subvert.gen;
i := i-1;
if IsBound(subvert.backptr) then
subvert := subvert.backptr;
else
dosub := false;
fi;
od;
fi;
if i>0 then level:=i-1; else level:=i; fi;
gct := gpref[level+1];
donesub := true;
fi;
fi;
if not donesub then
#Now we loop over the generator that is a candidate for
#substitution at this point.
for gen2 in [1..ngens] do
g2ltg1 := gen2 < gen1;
newdiff := table[diff][ng1*(gen1-1)+gen2];
if donesub then
donesub := true;
#i.e. do nothing - we really want to break from the for loop here.
elif newdiff=identity then
if deqi then #only occurs when gen2 and gen1 are equal in group
if g2ltg1 then
w[level] := gen2;
if level>1 then level:=level-2; else level:=level-1; fi;
gct := gpref[level+1];
donesub := true;
fi;
elif gptr[diffct].sublen>0 then
#Make a substitution by a string of equal length.
w[level] := gen2;
i := level-1;
subvert := gptr[diffct];
dosub := true;
while dosub do
w[i] := subvert.gen;
i := i-1;
if IsBound(subvert.backptr) then
subvert := subvert.backptr;
else
dosub := false;
fi;
od;
if i>0 then level:=i-1; else level:=i; fi;
gct := gpref[level+1];
donesub := true;
fi;
elif newdiff>0 then
if cf[newdiff] then
#We have this word difference stored already, but we will check
#to see if the current string precedes the existing one.
i := gpref[level];
repeat
i := i+1;
subvert := gptr[i];
until subvert.diffno=newdiff;
olen := subvert.sublen;
if deqi then
if g2ltg1 then nlen:=1; else nlen:= -1; fi;
else
l := gptr[diffct].sublen;
if l>0 then nlen:=l+1; else nlen:=l-1; fi;
fi;
if nlen > olen then # new string is better than existing one
subvert.gen := gen2;
subvert.sublen := nlen;
if deqi then Unbind(subvert.backptr);
else subvert.backptr := gptr[diffct];
fi;
fi;
else
# this is a new word-difference at this level, so
# we define a new vertex.
gct := gct+1;
gptr[gct] := rec();
if deqi then
if g2ltg1 then nlen:=1; else nlen:= -1; fi;
else
l := gptr[diffct].sublen;
if l>0 then nlen:=l+1; else nlen:=l-1; fi;
fi;
subvert := gptr[gct];
subvert.gen := gen2;
subvert.diffno := newdiff;
subvert.sublen := nlen;
if not deqi then subvert.backptr := gptr[diffct]; fi;
cf[newdiff] := true;
fi;
fi;
od; # End of loop over gen2
if not donesub then
#Go on to next word-difference from the previous level
if diff=identity then
if level=1 then
donediffs := true;
else
diffct := gpref[level-1] + 1;
fi;
else
diffct := diffct+1;
fi;
if not donesub and not donediffs then
if diffct > gpref[level] then
donediffs := true;
else
diff := gptr[diffct].diffno;
fi;
fi;
fi;
fi;
od; #end of loop over word-differences at previous level
level := level+1;
gpref[level] := gct;
od;
return w;
end;
#############################################################################
##
#F ReduceWordRWS(<rws>,<w>) . . . . reduces a word using rewriting-system
##
## ReduceWordRWS reduces the word <w>, using the rewriting-system <rws>.
## <w> can be given either as a list of integers (internal format) or as
## a word in the generators of the underlying group or monoid.
## Either the reduction FSA, or one of the word-difference automata (in the
## automatic group case) must be defined for <rws>.
## In the latter case, the separate function ReduceWordWD is called.
##
## Public function.
ReduceWordRWS := function ( rws, w )
local fsa, pos, label, state, history, eqn, sublen, table, ng, i, word;
if not IsKBMAGRewritingSystemRep(rws) then
Error("First argument is not an KBMAG rewriting system.");
fi;
if not IsAvailableReductionRWS(rws) then
Error(
"Reduction algorithm unavailable. Run KnuthBendix or AutomaticStructure.");
fi;
if not IsList(w) and not IsWord(w) then
Error("Second argument is not a word or list.");
fi;
ng := Length(rws!.alphabet);
if IsWord(w) then
word :=true;
w:=ShallowCopy(WordToListRWS(w,rws!.alphabet));
else word := false;
fi;
if IsBound(rws!.warningOn) and rws!.warningOn then
if IsBound(rws!.KBRun) and rws!.KBRun then
Print(
"#WARNING: system is not confluent, so reductions may not be to normal form.\n"
);
else
Print(
"#WARNING: word-difference reduction machine is not proven correct,\n",
" so reductions may not be to normal form.\n");
fi;
rws!.warningOn:=false;
# only give the warning once, or it could become irritating!
fi;
if IsBound(rws!.diff2) then
# automatic group case
w := ReduceWordWD(rws!.diff2,w);
elif IsBound(rws!.diff1c) then
# automatic group case
w := ReduceWordWD(rws!.diff1c,w);
elif IsBound(rws!.diff1) then
# automatic group case
w := ReduceWordWD(rws!.diff1,w);
elif IsBound(rws!.reductionFSA) then
fsa := rws!.reductionFSA;
if not IsInitializedFSA(fsa) or IsDeterministicFSA(fsa)=false then
Error("First argument does not have initialized dfa as field.");
fi;
state := fsa.initial[1];
pos := 1;
history:= [];
history[1] := state; # history[i] = state before reading i-th symbol.
table := DenseDTableFSA(fsa);
while pos <= Length(w) do
state := table[state][w[pos]];
if state>0 then
pos := pos+1;
history[pos] := state;
else
state := -state;
eqn := rws!.equations[state];
sublen := Length(eqn[1]);
SubstitutedListFSA(w,pos-sublen+1,pos,eqn[2]);
pos := pos-sublen+1;
state := history[pos];
fi;
od;
else
Error("First argument does not have initialized dfa as field.");
fi;
if not rws!.hasOne and Length(w)=0 then
Error("The empty word does not represent an element of a semigroup.");
fi;
if word then
w := ListToWordRWS(w,rws!.alphabet);
fi;
return w;
end;
#############################################################################
##
#F SizeRWS(<rws>>) . . . . . number of reduced words in a rewriting system
##
## This merely calls the corresponding FSA function.
##
## Public function.
SizeRWS := function ( rws )
if not IsKBMAGRewritingSystemRep(rws) then
Error("First argument is not a rewriting system.");
fi;
if not IsAvailableSizeRWS(rws) then
Error(
"Size algorithm unavailable. Run KnuthBendix or AutomaticStructure.");
fi;
if IsBound(rws!.warningOn) and rws!.warningOn then
if rws!.KBRun then
Print(
"#WARNING: system is not confluent, so size returned may not be correct.\n"
);
else
Print(
"#WARNING: word-difference reduction machine is not proven correct,\n",
" so size returned may not be correct.\n");
fi;
rws!.warningOn:=false;
# only give the warning once, or it could become irritating!
fi;
if IsBound(rws!.wa) then
# automatic group case
return LSizeDFA( rws!.wa );
fi;
return LSizeDFA( rws!.reductionFSA );
end;
#############################################################################
##
#F EnumerateRWS(<rws>, <min>, <max>) . . . enumerate reduced words in a rws
##
## This merely calls the corresponding FSA function.
## Words are converted to words in generators of underlying group or monoid
## before returning.
##
## Public function.
EnumerateRWS := function ( rws, min, max )
local ret, x, i;
if not IsKBMAGRewritingSystemRep(rws) then
Error("First argument is not a rewriting system.");
fi;
if not IsAvailableSizeRWS(rws) then
Error(
"Enumeration algorithm unavailable. Run KnuthBendix or AutomaticStructure.");
fi;
if IsBound(rws!.wa) then
# automatic group case
ret := LEnumerateDFA( rws!.wa,min,max );
else
ret := LEnumerateDFA( rws!.reductionFSA,min,max );
fi;
return ret;
end;
#############################################################################
##
#F SortEnumerateRWS(<rws>, <min>, <max>) . . enumerate reduced words and sort
##
## This merely calls the corresponding FSA function.
## Words are converted to words in generators of underlying group or monoid
## before returning.
##
## Public function.
SortEnumerateRWS := function ( rws, min, max )
local ret, x, i;
if not IsKBMAGRewritingSystemRep(rws) then
Error("First argument is not a rewriting system.");
fi;
if not IsAvailableSizeRWS(rws) then
Error(
"Enumeration algorithm unavailable. Run KnuthBendix or AutomaticStructure.");
fi;
if IsBound(rws!.wa) then
# automatic group case
ret := SortLEnumerateDFA( rws!.wa,min,max );
else
ret := SortLEnumerateDFA( rws!.reductionFSA,min,max );
fi;
return ret;
end;
#############################################################################
##
#F SizeEnumerateRWS(<rws>, <min>, <max>) . . . . number of reduced words
##
## This merely calls the corresponding FSA function.
##
## Public function.
SizeEnumerateRWS := function ( rws, min, max )
if not IsKBMAGRewritingSystemRep(rws) then
Error("First argument is not a rewriting system.");
fi;
if not IsAvailableSizeRWS(rws) then
Error(
"Enumeration algorithm unavailable. Run KnuthBendix or AutomaticStructure.");
fi;
if IsBound(rws!.wa) then
# automatic group case
return SizeLEnumerateDFA( rws!.wa,min,max );
fi;
return SizeLEnumerateDFA( rws!.reductionFSA,min,max );
end;
#############################################################################
##
#F OrderRWS(<rws>,<w>) . . . . order of word <w> in group or monoid
##
## OrderRWS tries to calculate the order of the element represented by the
## word <w> in the group or monoid of the rewriting system <rws>.
## Either the word-acceptor (automatic group case) or the reduction FSA
## must be defined.
## It could conceivably not terminate, but I have never known that happen!
##
## Public function.
OrderRWS := function ( rws, w )
local i, ng, fsa, prefix, preford, pt, t, targets, sufford, tracing, x,
z, cr, l;
if not IsKBMAGRewritingSystemRep(rws) then
Error("First argument is not an KBMAG rewriting system.");
fi;
if not rws!.hasOne then
Error("Order algorithm is only possible in a monoid or group");
fi;
if not IsAvailableReductionRWS(rws) then
Error(
"Reduction algorithm unavailable. Run KnuthBendix or AutomaticStructure.");
fi;
if not IsList(w) and not IsWord(w) then
Error("Second argument is not a word or list.");
fi;
ng := Length(rws!.alphabet);
if IsWord(w) then
w:=ShallowCopy(WordToListRWS(w,rws!.alphabet));
fi;
w := ReduceWordRWS(rws, w);
if Length(w)=0 then
return 1;
fi;
if IsBound(rws!.wa) then
# Automatic group case - use word-acceptor
fsa := rws!.wa;
else
fsa := rws!.reductionFSA;
fi;
prefix := w;
preford := 1;
while true do
#Check prefix is cyclically reduced
cr := true;
while cr do
l := Length(prefix);
if l>1 and rws!.invAlphabet[prefix[1]]=prefix[l] then
#remove first and last terms of prefix, but we must also
#perform the same conjugation operation on w.
w:=Concatenation([prefix[l]],w,[prefix[1]]);
w := ReduceWordRWS(rws,w);
prefix := prefix{[2..l-1]};
else
cr := false;
fi;
od;
#First see if all powers of prefix are reduced - if so, then a
#state of fsa will eventually repeat on tracing w^n, and w will have
#infinite order.
pt := WordTargetDFA(fsa, prefix);
t := pt;
targets := Set([t]);
tracing:=true;
while tracing do
for x in prefix do
t := TargetDFA(fsa, x, t);
if t<=0 then
break;
fi;
od; #for x in prefix
if t<=0 then
tracing := false;
elif t in targets then
return infinity;
else
AddSet(targets,t);
fi;
od; # while tracing
#not all powers of prefix are reduced, so we need to replace prefix
#by reduced word for a higher power.
sufford := 0;
tracing := true;
t := pt;
while tracing do
sufford := sufford+1;
for x in w do
t := TargetDFA(fsa, x, t);
if t<=0 then
tracing := false;
for i in [1..sufford] do
prefix := Concatenation(prefix,w);
od;
prefix := ReduceWordRWS(rws, prefix);
preford := preford + sufford;
if Length(prefix)=0 then
return preford;
fi;
#To improve chance of proving order infinite, we replace
#el and w by cyclic conjugates.
z := rws!.invAlphabet[prefix[1]];
if z <> false then
w:=Concatenation([z],w,[prefix[1]]);
w := ReduceWordRWS(rws,w);
prefix:=Concatenation([z],prefix,[prefix[1]]);
prefix := ReduceWordRWS(rws,prefix);
fi;
break;
fi;
od; #for x in w
od; #while tracing
od; #while true
end;
#############################################################################
##
#F AddOriginalEqnsRWS(<rws>).
## . . . . add original equations to rws after a call of KBRWS.
##
## This appends the original equations to the list of equations, after a
## call of KBRWS. Useful for a re-check, if the external program may have
## deleted some equations.
## After this function, rewriting is no longer possible.
## Public function.
AddOriginalEqnsRWS := function ( rws )
if not IsKBMAGRewritingSystemRep(rws) then
Error("First argument is not a rewriting system.");
fi;
Unbind(rws!.reductionFSA);
Unbind(rws!.isConfluent);
if IsBound(rws!.originalEquations) then
Append(rws!.equations,rws!.originalEquations);
fi;
end;
#############################################################################
##
#F KBRWS(<rws>) . . . . call external Knuth-Bendix program on rws
##
## This returns true if a confluent rewriting system results - otherwise
## false. In the latter case, words can still be rewritten with respect to
## the current equations, but they are not guaranteed to reduce to the unique
## representative of the group element.
## An error message results if the external program aborts without outputting.
## Public function.
KBRWS := function ( rws )
local O, callstring;
if not IsKBMAGRewritingSystemRep(rws) then
Error("First argument is not a rewriting system.");
fi;
if IsConfluentRWS(rws) then
Print("#The rewriting system is already confluent.\n");
Print("#Call - ResetRWS(<rws>) to restart.\n");
return fail;
fi;
#If we have already run KBRWS then the original equations will
#have been kept and should be re-inserted.
AddOriginalEqnsRWS(rws);
#Keep the original equations, in case we want them again.
if not IsBound(rws!.originalEquations) then
rws!.originalEquations := StructuralCopy(rws!.equations);
fi;
WriteRWS(rws,_KBTmpFileName);
callstring := Concatenation(Filename(_KBExtDir,"kbprog")," ",_KBTmpFileName);
Info(InfoRWS,1,"Calling external Knuth-Bendix program.");
Info(InfoRWS,3," ", callstring);
Exec(callstring);
UpdateRWS(rws,_KBTmpFileName,true);
Exec(Concatenation("/bin/rm -f ",_KBTmpFileName,"*"));
Info(InfoRWS,1,"External Knuth-Bendix program complete.");
if rws!.isConfluent then
O := rws!.options;
if IsBound(O.maxstoredlen) or IsBound(O.maxoplen) then
Print(
"#WARNING: Because of the control parameters you set, the system may\n");
Print(
"# not be confluent. Unbind the parameters and re-run KnuthBendix\n");
Print(
"# to check!\n");
rws!.isConfluent:=false;
fi;
fi;
if rws!.isConfluent then
Info(InfoRWS,1,"System computed is confluent.");
rws!.isAvailableNormalForm := true;
rws!.warningOn := false;
else
Info(InfoRWS,1,"System computed is NOT confluent.");
rws!.isAvailableNormalForm := false;
rws!.warningOn := true;
fi;
rws!.KBRun := true;
rws!.isAvailableReduction := true;
rws!.isAvailableSize := true;
return rws!.isConfluent;
end;
#############################################################################
##
#F AutRWS(<rws>, [<large>], [<filestore>], [<diff1>])
## . . . . call external automatic group program on rws
##
## This returns true if the automatic group programs succeed - otherwise
## false.
## The optional parameters are all boolean, and false by default.
## <large> means problem is large - the external programs use bigger tables.
## <filestore> means external programs use less core memory and more external
## files - they run a little slower.
## <diff1> is necessary on some examples - see manual for information.
## Public function.
AutRWS := function ( arg )
local narg, rws, large, filestore, diff1, callstring, optstring;
narg := Number(arg);
if narg<1 or not IsKBMAGRewritingSystemRep(arg[1]) then
Error("First argument is not a rewriting system.");
fi;
rws := arg[1];
if not IsGroupRWS(rws) then
Error("AutRWS can only be applied when all generators have inverses.");
fi;
if IsBound(rws!.KBRun) and rws!.KBRun then
Print("Knuth-Bendix has already been run on this rewriting system.\n");
Print("Call - ResetRWS( <rws> ) before proceeding.\n");
return;
fi;
if not rws!.ordering = "shortlex" then
Error("AutRWS only works for shortlex ordering");
fi;
large:=false; filestore:=false; diff1:=false;
if narg>=2 and arg[2]=true then large:=true; fi;
if narg>=3 and arg[3]=true then filestore:=true; fi;
if narg>=4 and arg[4]=true then diff1:=true; fi;
WriteRWS(rws,_KBTmpFileName);
callstring := Filename(_KBExtDir,"autgroup");
optstring := " ";
if large then optstring := Concatenation(optstring," -l "); fi;
if filestore then optstring := Concatenation(optstring," -f "); fi;
if diff1 then optstring := Concatenation(optstring," -d "); fi;
if InfoLevel(InfoRWS)=0 then
optstring := Concatenation(optstring," -s "); fi;
if InfoLevel(InfoRWS)>1 then
optstring := Concatenation(optstring," -v "); fi;
if InfoLevel(InfoRWS)>2 then
optstring := Concatenation(optstring," -vv "); fi;
callstring := Concatenation(callstring,optstring,_KBTmpFileName);
Info(InfoRWS,1,"Calling external automatic groups program.");
Info(InfoRWS,3," ", callstring);
Exec(callstring);
callstring := Filename(_KBExtDir,"gpminkb");
optstring := " ";
if InfoLevel(InfoRWS)=0 then
optstring := Concatenation(optstring," -s "); fi;
if InfoLevel(InfoRWS)>1 then
optstring := Concatenation(optstring," -v "); fi;
if InfoLevel(InfoRWS)>2 then
optstring := Concatenation(optstring," -vv "); fi;
callstring := Concatenation(callstring,optstring,_KBTmpFileName);
if READ(Concatenation(_KBTmpFileName,".success")) then
Info(InfoRWS,1,
"Computation was successful - automatic structure computed.");
Info(InfoRWS,3," ", callstring);
Exec(callstring);
UpdateRWS(rws,_KBTmpFileName,false);
Exec(Concatenation("/bin/rm -f ",_KBTmpFileName,"*"));
rws!.isAvailableNormalForm := true;
rws!.isAvailableReduction := true;
rws!.isAvailableSize := true;
rws!.warningOn := false;
return true;
else
Exec(Concatenation("/bin/rm -f ",_KBTmpFileName,"*"));
Info(InfoRWS,1,"Computation was not successful.");
return false;
fi;
end;
#############################################################################
## The remaining functions in the file enable the user to to call the
## different parts of the automata program individually.
## They are experimental and less well supported than KBRUN and AutRWS.
#############################################################################
##
#F KBWD(<rws>, [<haltingfactor>], [<large>])
## . . . . call external Knuth-Bendix program with -wd on rws
##
## Runs KBRUN, computes word differences, and sets the diff1 and diff2 flags
## of rws to be the appropriate difference machines.
## An error message results if the external program aborts without outputting.
## Public function.
KBWD := function ( arg )
local narg,rws, haltingfactor,large, callstring, optstring, mg, IdWord;
narg := Number(arg);
if narg<1 or not IsKBMAGRewritingSystemRep(arg[1]) then
Error("First argument is not a rewriting system.");
fi;
large:=false; haltingfactor:=100;
rws := arg[1];
if not IsGroupRWS(rws) then
Error("KBWD can only be applied when all generators have inverses.");
fi;
if IsBound(rws!.KBRun) and rws!.KBRun then
Print("Knuth-Bendix has already been run on this rewriting system.\n");
Print("Call - ResetRWS( <rws> ) before proceeding.\n");
fi;
if narg>1 then haltingfactor := arg[2]; fi;
if narg>2 then large := arg[3]; fi;
WriteRWS(rws,_KBTmpFileName);
callstring := Concatenation(Filename(_KBExtDir,"kbprog")," -wd -hf ");
callstring := Concatenation(callstring,String(haltingfactor)," ");
optstring := "";
if large then
optstring := Concatenation(optstring," -cn 0 -me 262144 -t 500 ");
fi;
if InfoLevel(InfoRWS)=0 then
optstring := Concatenation(optstring," -silent "); fi;
if InfoLevel(InfoRWS)>1 then
optstring := Concatenation(optstring," -v "); fi;
if InfoLevel(InfoRWS)>2 then
optstring := Concatenation(optstring," -vv "); fi;
callstring := Concatenation(callstring,optstring,_KBTmpFileName);
Info(InfoRWS,1,
"Calling external Knuth-Bendix program for word-differences.");
Info(InfoRWS,3," ", callstring);
Exec(callstring);
Info(InfoRWS,1,"External Knuth-Bendix program complete.");
StoreNamesRWS(rws,_KBTmpFileName);
if not READ(Concatenation(_KBTmpFileName,".diff1")) then
Error("Could not open diff1 file");
fi;
if not READ(Concatenation(_KBTmpFileName,".diff2")) then
Error("Could not open diff2 file");
fi;
if not READ(Concatenation(_KBTmpFileName,".kbprog.ec")) then
Error("Could not open exit-code file");
fi;
rws!.diff1 := _RWS.diff1;
rws!.diff2 := _RWS.diff2;
RedefineNamesRWS(rws,_KBTmpFileName);
InitializeFSA(rws!.diff1);
rws!.diff1.alphabet.base.printingStrings:=List(rws!.alphabet,x->String(x));
rws!.diff1.states.printingStrings:=List(rws!.alphabet,x->String(x));
DenseDTableFSA(rws!.diff1);
rws!.diff1.table.format:="dense deterministic";
rws!.diff1.table.transitions:=rws!.diff1.denseDTable;
Unbind(rws!.diff1.sparseTable);
InitializeFSA(rws!.diff2);
rws!.diff2.alphabet.base.printingStrings:=List(rws!.alphabet,x->String(x));
rws!.diff2.states.printingStrings:=List(rws!.alphabet,x->String(x));
DenseDTableFSA(rws!.diff2);
rws!.diff2.table.format:="dense deterministic";
rws!.diff2.table.transitions:=rws!.diff2.denseDTable;
Unbind(rws!.diff2.sparseTable);
if _ExitCode=2 then
Print(
"#WARNING: Knuth-Bendix program terminated with halting factor condition\n");
Print(" not satisfied.\n");
return false;
fi;
rws!.isAvailableReduction := true;
rws!.warningOn := true;
Exec(Concatenation("/bin/rm -f ",_KBTmpFileName,"*"));
return true;
end;
#############################################################################
##
#F GpWA(<rws>, [<large>], [<filestore>], [<diff1>])
## . . . . call external word-acceptor program on rws
##
## This assumes that KBWD has already been called on rws
## Public function.
GpWA := function ( arg )
local narg, rws, large, filestore, diff1, callstring, optstring;
narg := Number(arg);
if narg<1 or not IsKBMAGRewritingSystemRep(arg[1]) then
Error("First argument is not a rewriting system.");
fi;
rws := arg[1];
if not rws!.ordering = "shortlex" then
Error("Ordering must be shortlex for external word-acceptor program");
fi;
large:=false; filestore:=false; diff1:=false;
if narg>=2 and arg[2]=true then large:=true; fi;
if narg>=3 and arg[3]=true then filestore:=true; fi;
if narg>=4 and arg[4]=true then diff1:=true; fi;
if diff1 then
WriteFSA(
rws!.diff1,"_RWS.diff1",Concatenation(_KBTmpFileName,".diff1"),";");
else
WriteFSA(
rws!.diff2,"_RWS.diff2",Concatenation(_KBTmpFileName,".diff2"),";");
fi;
callstring := Filename(_KBExtDir,"gpwa");
optstring := " ";
if large then optstring := Concatenation(optstring," -l "); fi;
if filestore then optstring := Concatenation(optstring," -f "); fi;
if diff1 then optstring := Concatenation(optstring," -d "); fi;
if InfoLevel(InfoRWS)=0 then
optstring := Concatenation(optstring," -silent ");
fi;
if InfoLevel(InfoRWS)>1 then
optstring := Concatenation(optstring," -v ");
fi;
if InfoLevel(InfoRWS)>2 then
optstring := Concatenation(optstring," -vv ");
fi;
callstring := Concatenation(callstring,optstring,_KBTmpFileName);
Info(InfoRWS,1,"Calling external word-acceptor program.");
Info(InfoRWS,3," ", callstring);
Exec(callstring);
Info(InfoRWS,1,"External word-acceptor program complete.");
StoreNamesRWS(rws,_KBTmpFileName);
if not READ(Concatenation(_KBTmpFileName,".wa")) then
Error("Could not open wa file");
fi;
rws!.wa := _RWS.wa;
RedefineNamesRWS(rws,_KBTmpFileName);
InitializeFSA(rws!.wa);
rws!.wa.alphabet.printingStrings:=List(rws!.alphabet,x->String(x));
rws!.isAvailableSize := true;
rws!.warningOn := true;
Exec(Concatenation("/bin/rm -f ",_KBTmpFileName,"*"));
end;
#############################################################################
##
#F GpGenMult(<rws>, [<large>], [<filestore>], [<diff1>] )
## . . . . call external generalised multiplier program on rws
##
## This assumes that KBWD and GpWA have already been called on rws
## Public function.
GpGenMult := function ( arg )
local narg, rws, large, filestore, diff1, callstring, optstring;
--> --------------------
--> maximum size reached
--> --------------------
