✦ LIBER ✦

An Optimal Algorithm for Constructing the Reduced Gröbner Basis of Binomial Ideals

✍ Scribed by Ulla Koppenhagen; Ernst W. Mayr

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 642 KB
Volume: 28
Category: Article
ISSN: 0747-7171
DOI: 10.1006/jsco.1999.0285

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we present an optimal, exponential space algorithm for generating the reduced Gröbner basis of binomial ideals. We make use of the close relationship between commutative semigroups and pure difference binomial ideals. Based on an optimal algorithm for the uniform word problem in commutative semigroups, we first derive an exponential space algorithm for constructing the reduced Gröbner basis of pure difference binomial ideals. In addition to some applications to finitely presented commutative semigroups, this algorithm is then extended to an exponential space algorithm for generating the reduced Gröbner basis of binomial ideals over Q in general.

📜 SIMILAR VOLUMES

An Optimal Algorithm for Constructing th

An Optimal Algorithm for Constructing the Reduced Gröbner Basis of Binomial Ideals, and Applications to Commutative Semigroups

✍ Ulla Koppenhagen; Ernst W. Mayr 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 404 KB

It is known that the reduced Gröbner basis of general polynomial ideals can be computed in exponential space. The algorithm, obtained by Kühnle and Mayr, is, however, based on rather complex parallel computations, and, above that, makes extensive use of the parallel computation thesis. In this paper