Some complexity results for prefix Gröbner bases in free monoid rings

We establish the following complexity results for prefix Gröbner bases in free monoid rings: 1. |R|⋅size(p) reduction steps are sufficient to normalize a given polynomial p w.r.t. a given right-normalized system R of prefix rules compatible with some total admissible well-founded ordering >. 2. O(|R|⋅size(R)) basic steps are sufficient to transform a given terminating system R of prefix rules into an equivalent right-normalized system. 3. O(|R|2⋅size(R)) basic steps are sufficient to decide whether or not a given terminating system R of prefix rules is a prefix Gröbner basis. The latter result answers an open question posed by Zeckzer (2000) [9].