We are concerned with functions over words which are computable by means of a rewrite system admitting polynomial interpretation termination proofs.

We classify them according to the interpretations of successor symbols. This leads to the definition of three classes, which turn out to be exactly the poly-time, linear exponential-time and doubly linear exponential time computable functions. As a consequence, we also characterize the linear space computable functions.