[GAP Forum] "Knuth-Bendix Rewriting Confluent" hangs

[Robert Eckert]

The problem I am attempting is verifying the correctness and completeness
of free-mod-relations for the sporadic pure-braid groups:  here "full" is
a free group modulo a set of "brds" braid-relations; "weyl" is also modulo
the "sqrs" letters-squared; "pure" should be the kernel of the map from
"full" to "weyl" and is claimed to be "gens" mod "rels"; the correctness
check is whether all the rels are actually trivial under the brds; the
completeness check is whether there are any other true relations among the
gens independent of rels.  Here is the file for C2, a small case
(symmetries of the square):

c2:=FreeGroup(2);
c2brds:=[c2.1*c2.2*c2.1*c2.2*c2.1^-1*c2.2^-1*c2.1^-1*c2.2^-1];
c2sqrs:=[c2.1^2,c2.2^2];
 a12:=c2.1*c2.1;
 a23:=c2.2*c2.2;
 a13:=c2.2*c2.1*c2.1*c2.2^-1;
 b23:=c2.1*c2.2*c2.2*c2.1^-1;
c2gens:=[a12,a23,a13,b23];
r1:=Comm(a23,b23*a12*a13);
r2:=Comm(a13,a23*b23*a12);
r3:=Comm(a12,a13*a23*b23);
c2rels:=[r1,r2,r3];
c2full:=c2/c2brds;
c2weyl:=c2/Union(c2brds,c2sqrs);
c2pure:=Subgroup(c2,c2gens)/c2rels;
c2fhom:=GroupHomomorphismByImages(c2,c2full,GeneratorsOfGroup(c2),GeneratorsOfGroup(c2full));
c2errs:=Image(c2fhom,c2rels);
correct:=IsTrivial(c2errs);
c2whom:=GroupHomomorphismByImages(c2full,c2weyl,GeneratorsOfGroup(c2full),GeneratorsOfGroup(c2weyl));
c2phom:=GroupHomomorphismByImages(c2pure,Kernel(c2whom),GeneratorsOfGroup(c2pure),Image(c2fhom,c2gens));
c2gaps:=Kernel(c2phom);
complete:=IsTrivial(c2gaps);

The correctness question is whether c2rels is in the normal closure of
c2brds.  Asking for NormalClosure(c2,c2brds) gives a Reidemeister-Schreier
process with infinite coset traversal:  old versions crashed with "coset
enumeration exceeds 256000" while 4.4 just refuses "No Method Found".  The
homomorphism trivializing c2brds will define, but then asking for the
image under that hom sends it into "MakeKnuthBendixRewritingConfluent"
forever and ever:  the log-file shows it dying between the definition of
c2fhom and c2errs, after a 45-minute run, from memory exhaustion.  For the
completeness test it needs to construct Kernel(c2whom), which is what the
pure-braid group really is, to get c2phom from the claimed "pure" to the
real "pure"; this hangs in a same way (I killed it after 90 minutes).
Is there another way to do this?  Or would either one of these, done as
above, eventually finish given enough time and space?
-------------- next part --------------
gap> Read("a:\C2a.gap");time;correct;complete;
user interrupt at
p := 0;
 called from
KBOverlaps( i[1], i[2], kbrws, p ) called from
KB_REW.MakeKnuthBendixRewritingSystemConfluent( rws ); called from
MakeKnuthBendixRewritingSystemConfluent( kbrws ); called from
MakeConfluent( kbrws ); called from
ReducedConfluentRewritingSystem( M, wordord ) called from
...
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> return;
exceeded the permitted memory (`-o' command line option) at
Append( l, [ [ i, n ], [ n, i ] ] );
 called from
add_rule( [ a, b ], kbrws ); called from
AddRuleReduced( kbrws, [ a, c ] ); called from
KBOverlaps( i[1], i[2], kbrws, p ) called from
KB_REW.MakeKnuthBendixRewritingSystemConfluent( rws ); called from
MakeKnuthBendixRewritingSystemConfluent( kbrws ); called from
...
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> quit;
gap> time;
2720266
gap> c2errs;
Variable: 'c2errs' must have a value

gap> c2fhom;
[ f1, f2 ] -> [ f1, f2 ]
gap> c2whom:=GroupHomomorphismByImages(c2full,c2weyl,GeneratorsOfGroup(c2full),GeneratorsOfGroup(c2weyl));
[ f1, f2 ] -> [ f1, f2 ]
gap> c2phom:=GroupHomomorphismByImages(c2pure,Kernel(c2whom),GeneratorsOfGroup(c2pure),Image(c2fhom,c2gens));
user interrupt at
Append( l, [ [ i, n ], [ n, i ] ] );
 called from
add_rule( [ a, b ], kbrws ); called from
AddRuleReduced( kbrws, [ a, c ] ); called from
KBOverlaps( i[1], i[2], kbrws, p ) called from
KB_REW.MakeKnuthBendixRewritingSystemConfluent( rws ); called from
MakeKnuthBendixRewritingSystemConfluent( kbrws ); called from
...
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> quit:
Syntax error: ; expected in *errin* line 1
quit:
    ^
brk> quit;
gap> time
> ;
5460140
gap> quit;