Hi,
I've been playing with my algebra code again and rewriting it to behave
more like the rest of Maxima: I keep stumbling around and then suddenly
realising how everyone else has been solving a problem for the last two+
decades and going "Oh, that's sensible". Anyway, the latest problem is:
If you define a monoid or a semigroup (say) by a set of generators and
relations and want to do any computations with elements, you need a
rewriting system (sometimes called a Thue system), which can (sort of)
be built using the Knuth-Bendix algorithm. Doing so can be
computationally expensive. I would like to have code that a user could
use something like this:
SG: semigroup ([a,b], [a.b = b.a]);
/* SG is the free abelian semigroup on two generators. No computation
should be done yet */
normal_form (algebraic_expression (a.b.a.b.a.b, SG));
/* Here I'm asking for a normal form for some word. Cue heavy
machinery to try and make a confluent rewriting system for SG. If
SG were more complicated this might take a long (unbounded!) time,
although I'll make options to allow the user to give up and then
restart etc. */
/* Once that's worked, I want another call for a normal form for an
element of SG to be really quick. */
I've written a (reasonably lame) Knuth-Bendix implementation together
with several iterations of front end code to make a syntax something
like the above work, but I'm not sure how to store the rewriting system
for SG.
One option would be to stick it in SG itself, in the CAR say, so it
doesn't get printed. This seems reasonable, but the simplifier (via
simpargs) sometimes seems to eat stuff stored there. As far as I can see
that happens exactly when SG is changed via a simplification: is this
written down somewhere so I can depend on it? If this doesn't happen,
there is also a problem from sessions like this:
SG: semigroup([a,b], [a.b = b.a]);
/* do stuff that forces computation of the rewriting system */
SG: subst (b.a.a, b.a, SG);
/* oh noes, maybe the rewriting system is wrong? */
If I can't depend on this behaviour, another option would be storing
some dictionary keyed by generator and relation lists with EQUALP. This
would definitely work, but if someone keeps changing the semigroups that
they work with, it'll "leak memory" since I don't have any way of
discarding the rewriting systems that can't be used any more.
Anyway, I thought that someone here must have solved this problem for
another use and could maybe point me at an example for the right thing
to do!
Thanks in advance for any help,
Rupert
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 315 bytes
Desc: not available
URL: <http://www.math.utexas.edu/pipermail/maxima/attachments/20120726/6f698521/attachment.pgp>;