One way to graphically record the fact that a polynomial
*s* lies in the ideal generated by
is to create
a graph whose vertices are
and edges are
, , , , (each
of the edges is directed toward *s*).
By taking a finite union of graphs of the type just
described, one has a graph whose vertices are
polynomials and the following
property holds:

Every vertexSince the GBA is based on generating S-polynomials, its flow can be described as the construction of a graph with the above property and this graph will be directed and acyclic. Our implementation of the GBA actually constructs this graph and this graph is used in §. Also, note that ifvof the graph has no immediate ancestors or lies in the ideal generated by its immediate ancestors.

We now lay these observations into an abstract framework in the next section.

Wed Jul 3 10:27:42 PDT 1996