The graph

We begin with a standard definition about graphs. Let G=(V,E) be a graph and v be a vertex of G. We say that the immediate ancestors of v are members of the set T(v,G) of vertices from which there is an edge leading to v (i.e., ).

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 vertex v of the graph has no immediate ancestors or lies in the ideal generated by its immediate ancestors.

Since 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 if v is a vertex, then v is a starting polynomial equation for the run if and only if it has no immediate ancestors.

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