Login
- Dokumenttyp:
- Technical Report
- Autor(en):
- Ulla Koppenhagen; Ernst W. Mayr
- Titel:
- Optimal Gröbner Base Algorithms for Binomial Ideals
- Abstract:
- Little is known about upper complexity bounds for the normal form algorithms which transform a given polynomial ideal basis into Gröbner basis. In this paper, we exhibit an optimal, exponential space algorithm for generating the reduced Gröbner basis of binomial ideals. This result is then applied to derive space optimal decision procedures for the finite enumeration and subword problems for commutative semigroups.
- Stichworte:
- Finite Enumeration Problem; Subword Problem; Computational Complexity
- Jahr:
- 1996
- Jahr / Monat:
- 1996-01-01 00:00:00
- Seiten/Umfang:
- 18
BibTeX