Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleSome complexity results for prefix Gr\"obner bases in free monoid rings.
Author(s) Andrea Sattler-Klein
TypeBook, Chapter in Book, Conference Proceeding
AbstractWe establish the following complexity results for prefix Gröbner bases in free monoid rings: 1. ||⋅size(p) reduction steps are sufficient to normalize a given polynomial p w.r.t. a given right-normalized system  of prefix rules compatible with some total admissible wellfounded ordering >. 2. O(||2⋅size()) basic steps are sufficient to transform a given terminating system  of prefix rules into an equivalent right-normalized system. 3. O(||3⋅size()) basic steps are sufficient to decide whether or not a given terminating system  of prefix rules is a prefix Gröbner basis. The latter result answers an open question posed by Zeckzer in [10].
URL http://link.springer.com/chapter/10.1007%2F978-3-540-74240-1_41
PublisherBerlin: Springer
Translation No
Refereed No