Due to the errata in [1] Propositions 9, 10, Theorem 23, Corollary 24 have to be fixed as follows:

- Let R be a TRS ... + Let R be a non-duplicating TRS ...

Similarly, Lemma 17 should be rectified as follows:

- whenever ... + whenever R is non-duplicating and ...

As a consequence of the modifications, the proof of the linear runtime complexity of Example 1 has to be retracted.