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