Algorithm 628: An Algorithm for Constructing Canonical Bases of Polynomial Ideals
The notion of GrGbner bases for polynomial ideals, which is central to this paper, is given by the following: Definition. A finite set F of polynomials in K[xl, . . . , x,] is called a canonical basis or Grtibner basis (for the ideal generated by F) if and only if (GB) for arbitrary polynomials f, g, h E K[xl, . . . , x,]: if f +F g, f “F h, and g, h are irreducible modulo +F, then g = h. Here, ‘f +‘I? g” means that ‘f may be reduced to g modulo F m by applying a certain reduction process that may be considered as a “generalized division.” For the exact definition of this reduction relation and examples, we refer to [4] and [6]. (GB) is equivalent to the assertion that ‘F has the Church-Rosser property, whose fundamental importance in rewrite systems is well known (see, e.g., [22]). The problem of constructing Grijbner bases for polynomial ideals is characterized by the following: