I have heard that toric ideals allow one to speed up the Buchberger algorithm considerably (see Grobner bases of toric ideals, Remark 2,3). My question is two-fold:
What are the precise complexity-theoretic bounds known for the Buchberger algorithm for toric ideals?
Are there other non-trivial classes of ideals on whom a grobner basis can be computed efficiently? Can you please provide a reference to them?
For context, I wish to use a grobner basis as a way to encode dataflow analysis problems in compiler construction, in a manner that allows mutiple analyses to "share" information easily. So, knowing special types of ideals and fast algorithms to compute their Grobner basis woud help design specific dataflow analyses.
