The Computation of Gröbner Bases Using an Alternative Algorithm

When Zharkov and Blinkov ([ZB93]) applied the classical ideas of involutive systems originating from the theory of partial differential equations (c.f. [Ja29], [Po78]) to the computation of Grobner bases (c.f. [Bu65], [BW93]) their theory seemed to be a rather marginal concept. But due to the opportunity of gaining a faster version for one of the most frequently applied algorithms the method came into the focus of computer algebra research (c.f. [Ap95], [GB95], [GS95], [Ma95]). It turned out that Pommaret bases are not only of interest for fast implementations (c.f. [ZB93]) but that they are also a point of contact of different theories which were investigated intensively for a long time. So, the theory of Pommaret bases enables the exchange of useful ideas between the theories as well as it benefits itself from the relationships. A certain similarity of the Zharkov/Blinkov method and the Kandri-Rody/Weispfenning closure technique motivates the study of commutative polynomial rings from a non-commutative point of view. The theory of Pommaret bases can be presented in an algebraic way using the Grobner theory of graded structures. Here we will present the straight forward generalization of Pommaret bases to the class of algebras of solvable type. Under the non-commutative grading most calculations are pushed back to the free non-commutative polynomial ring. This provides a link to the theory of term rewriting and the Zharkov/Blinkov method appears as an application of the prefix reduction/saturation technique of Madlener and Reinert (c.f.[MR93]) with a restricted saturation. The restricted saturation has its natural origin in the syzygy theory and heavily improves the termination behaviour in the particular case of Pommaret bases. So, it seems to be worth to investigate the effect of splitting the saturation step also for similar term rewriting problems.