The F5 criterion revised (Q2275900)

Gröbner bases have played a crucial role in commutative algebra and many scientists had tried to improve the original Buchberger's algorithm and to detect useless computations [\textit{B. Buchberger}, Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideals. Ph.D. Thesis, University of Innsbruck. (1965); Lect. Notes Comput. Sci. 72, 3--21 (1979; Zbl 0417.68029); \textit{R. Gebauer} and \textit{M. Möller}, J. Symb. Comput. 6, No. 2/3, 275-286 (1988; Zbl 0675.13013); \textit{D. Lazard}, Lect. Notes Comput. Sci. 162, 146--156 (1983; Zbl 0539.13002)]. The authors present a simpler algorithm that illustrates the principle of the Faugère's ``F5'' algorithm and enables to remove various restrictions. By considering a function \(s\), the authors define new concepts such as primitive \(s\)-irreducible polynomials and \(s\)-Gröbner bases. From this new theory, it is developed a simpler algorithm which computes a \(s\)-Gröbner basis of an ideal. This new algorithm is different from the Faugère's algorithm and does not involve reductions that yield more than one result. In the end of the paper, the authors compare this algorithm with the Staggered Linear Basis algorithm of \textit{R. Gebauer} and \textit{M. Möller} [Buchberger's algorithm and staggered linear bases. in: Proceedings of SYMSAC 1986, Waterloo/Ontario, ACM Press. 218--221 (1986)] and with the \textit{J.-C. Faugère}'s ``F5'' criterion [ISSAC 2002. Proceedings of the 2002 international symposium on symbolic and algebraic computation, Lille, France, July 07--10, 2002. New York, NY: ACM Press. 75--83 (2002; Zbl 1072.68664)].