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.