This paper was invited by the editor, Victor Ufnarofski, for a special issue of the journal devoted to computer algebra. The joint papers with Helton on this work are addressed to an audience of engineers and are somewhat didactic. This paper presents the foundations of the topic more formally to a computer science audience in terms of rewrite rules. The paper also includes a short discussion of the special purpose system used in this work.

1.     Foundations

Gröbner Basis technology can be viewed as a chapter in non-commutative ring theory, concerned with ideals and ideal bases-with connections to algebraic geometry. It can also be seen as providing a reduction process akin to the rewrite rules used in computer science.This paper uses rewrite rules as the foundation.

2.     Operator Theory Models

The technology we introduce is applied to several "models" that arise in operator or matrix theory.  The original goal of this work was the simplification of complex expressions. The Gröbner technology was used to produce a complete set of simplifying expressions from various starting sets of relations.

3.     Other examples and results

The operator theory work produced situations in which the Basis Algorithm does not terminate and for which a Gröbner Basis exists but is infinite. This section examines some ways that infinite Gröbner Bases arise. It presents a simple example where the Gröbner Basis is finite for one term ordering and infinite for another.
 
Some of the operator theory models that arise in the work with Helton have infinite bases. Changing the "handedness" of a few rules causes the infinite families to collapse. The handedness of rules cannot be changed arbitrarily (it could, for example, produce a cycle in the graph) -- so a search was conducted for a valid term ordering which had this effect. The Wreath Product ordering (used by group theorists) was shown to accomplish this for the operator theory models. All of the operator theory models have finite Gröbner Bases when this ordering is used. (It is not, however, a "simplification order").  [After the publication a simpler order, the Elimination Order, was found to also produce finite bases for the operation theory models.]

4.    Discussion of research software and implementation

This research uses a special approach to the design and implementation of research software. The last section of the paper contains a brief discussion of this approach and provides some information about the base language (Forth) used in this work.