STACS 2007
Lecture Notes in Computer Science, 2007, Volume 4393/2007, 308-319, DOI: 10.1007/978-3-540-70918-3_27

An Exponential Lower Bound for Prefix Gröbner Bases in Free Monoid Rings

Andrea Sattler-Klein

View Related Documents

Abstract

We show by an example that the number of reduction steps needed to compute a prefix Gröbner basis in a free monoid ring by interreduction can in fact be exponential in the size of the input. This answers an open question posed by Zeckzer in [Ze00].

Keywords  algorithms - computational complexity - rewriting -  Gröbner bases.

Fulltext Preview

Image of the first page of the fulltext document