Details
- Autor(en) / Beteiligte
- Titel
- An Exponential Lower Bound for Prefix Gröbner Bases in Free Monoid Rings
- Ist Teil von
- STACS 2007, p.308-319
- Ort / Verlag
- Berlin, Heidelberg: Springer Berlin Heidelberg
- Link zum Volltext
- Quelle
- Alma/SFX Local Collection
- Beschreibungen/Notizen
- 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].
- Sprache
- Englisch
- Identifikatoren
- ISBN: 9783540709176, 3540709177ISSN: 0302-9743eISSN: 1611-3349DOI: 10.1007/978-3-540-70918-3_27Titel-ID: cdi_springer_books_10_1007_978_3_540_70918_3_27
- Format
- –
- Schlagworte
- algorithms, computational complexity, Gröbner bases, rewriting