An optimal algorithm for constructing the reduced Gröbner basis of binomial ideals (Q1974694)

The authors present an exponential space algorithm to obtain the reduced Gröbner basis of any binomial ideal in \(\mathbb{Q}[X_1, \dots, X_n]\) (that is, an ideal generated by monomials and differences of monomials). In a first step, they obtain an algorithm which generates the Gröbner basis of any pure difference binomial ideal using an algorithm for the uniform word problem in commutative semigroups [see \textit{E. W. Mayr} and \textit{A. R. Meyer}, Adv. Math. 46, 305-329 (1982; Zbl 0506.03007)]. They also show some applications of their algorithm to finitely presented commutative semigroups. Then, they extend the previous algorithm to an exponential space algorithm that obtains the reduced Gröbner basis of any binomial ideal over \(\mathbb{Q}\). As any algorithm for computing Gröbner bases of binomials ideals requires at least exponential space [see, for example, \textit{D. T. Huynh}, Inf. Control 68, 196-206 (1986; Zbl 0612.68033)], the authors state that their algorithms are optimal with respect to space.