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 Gröbner 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 Gröbner 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. The main result of this paper consists in the presentation of a termination condition for the Zharkov/Blinkov method providing an alternative algorithm for the computation of ordinary Gröbner bases which terminates for arbitrary ideals in the case of generalized degree compatible term orders.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:31850 |
| Date | 04 October 2018 |
| Creators | Apel, Joachim |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, doc-type:article, info:eu-repo/semantics/article, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 978-3-0348-8800-4 |
Page generated in 0.0024 seconds