Gröbner bases provide a universal technique for computer-algebraic treatment of algebraic and geometric problems. However, the question of structural complexity of Gröbner bases and that of the computational complexity of the relevant algorithms remain as yet practically open. The present paper contains a complete and constructive description of Gröbner bases for the class of two-variable polynomials over a field and that of univariate polynomials over a Euclidean ring. This description gives rise to a simple algorithm for computing primary decompositions. A natural factorization is also found for the resultant of two univariate polynomials.
Reviewer: A.Bocharov