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

[Robert Eckert]

On Thu, 29 Apr 2004, Christian Sievers wrote:

> Dear Robert, dear Forum,
>
> Robert Eckert asked about the FGA package:
>
> > Are there some useful new commands in there?  All I see written up is
> > "Centralizer".
>
> I certainly hope that the commands in the FGA package are useful.
Yes, they are.  My problem turned out to be just a glitch in the way the
manual was installed; in various sections, including most of the FGA info,
I would hit "?" and get the headers and zero text; this has been fixed.
...
> Most of the methods work with finitely generated subgroups of free groups.
> They allow a (constructive) membership test...
The problem, with groups not subgroups-of-free but quotient-groups modding
out some relations, is that it may falsely say a word is "not" in the
group, if it is distinguished from a word it would recognize by something
which, really, is trivial, but which it does not know how to trivialize.
This is not a fault of the packages but of the general "word problem".
Forcing Knuth-Bendix to run asks if this is in "the swamp", when, alas,
the swamp is bottomless.  Holt's KBMag package says, effectively, "let's
just map the top ten meters of the swamp".  Pardon me if I am asking a
"duh, of course!" or "duh, of course not!" question, but is there a way of
force-feeding a set of rules?  "Forget what Knuth-Bendix says looks
good, you will use THESE rules and like it"?  The problem may be that K-B
wants to find the shortening possibilities, where actually a rewriting
that makes most things longer is what some purposes need.
If I rewrite in an ugly set of generators, I can deploy a filtration,
pure-F4 = top-F4 semidirect product by pure-C3, which is top-C3 by
pure-C2, which is top-C2 by pure-A1, which is free on letter-1-squared.
For each high-grade generator G and lower-grade g there is exactly one
relation like
G g = g G' G" G G"- G'-
moving g left and replacing G with its conjugate by a varying number (zero
to hundreds) of generators at its same grade.  KBMag can guarantee me
something IS trivial, but this way can guarantee something is NOT trivial;
if all grades are separated, each graded component must be trivial (and
within each grade there are few relations:  all grade-2 and all type-A or
type-C at every grade are purely free; type-D and H3 have only one
commutator, the two blocks of which can be decreed to be two of the
generators; top-E6/E7/E8/F4/H4 are worse but not horribly so).
I have been fighting to make my home-brew program do this right for a
wearyingly long time, but I can get it to spit out its rules into a file
GAP can Read if there is code to pick up the ball from there.
> All the best
  Bob Eckert