Rewriting systems in GAP are a framework for dealing with the very general task of rewriting elements of a free (or term) algebra in some normal form. Although most rewriting systems currently in use are string rewriting systems (where the algebra has only one binary operation which is associative) the framework in GAP is general enough to encompass the task of rewriting algebras of any signature from groups to semirings.
Rewriting systems are already implemented in GAP for finitely presented semigroups and for pc groups. The use of these particular rewriting systems is described in the corresponding chapters. We describe here only the general framework of rewriting systems with a particular emphasis on material which would be helpful for a developer implementing a rewriting system.
We fix some definitions and terminology for the rest of this chapter. Let T be a term algebra in some signature. A term rewriting system for T is a set of ordered pairs of elements of T of the form (l, r). Viewed as a set of relations, the rewriting system determines a presentation for a quotient algebra A of T.
When we take into account the fact that the relations are expressed as ordered pairs, we have a way of reducing the elements of T. Suppose an element u of T has a subword l and (l,r) is a rule of the rewriting system, then we can replace the subterm l of u by the term r and obtain a new word v. We say that we have rewritten u as v. Note that u and v represent the same element of A. If u can not be rewritten using any rule of the rewriting system we sat that u is reduced.
[Top] [Previous] [Up] [Next] [Index]
GAP 4 manual