[GAP Forum] "Knuth-Bendix Rewriting Confluent" hangs
Alexander Hulpke
hulpke at math.colostate.edu
Mon May 3 16:59:20 BST 2004
Dear GAP-Forum,
Robert Eckert wrote:
> 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
While I'm not 100% certain on this interpretation, I understand yoiur
question as asking whether you can prescribe your own rewriting rules.
This is possible (see the manual chapter on rewriting systems). However in
this case:
- you will have to ensure confluence on your own. (which can be
nontrivial).
- Unless you substitute your rewriting system (for this you would have to
change the library code), you will have to call `ReducedForm' with monoid
elements and cannot simply do group arithmetic.
> 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
What you are doing effectively is to work in some quotient group. GAP can
get you some of these (see e.g. `SolvableQuotient').
In principle you could try to generalize existing code to work even in a
profinite quotient. The problem then becomes to know when to stop evaluating
to prove (non)-equality of elements.
Best wishes,
Alexander Hulpke
More information about the Forum
mailing list