Little is known about upper complexity bounds for the normal form algorithms which transform a given polynmial ideal basis into a Grobner basis. In this paper, we exhibit an optimal, exonential space algorithm for generating the reduced grobner basis of binomial ideals. This result is then applied to derive space optimal decision procedures for the finite enumeration and subword problems for commutative semi-groups.
展开▼
