Dieter Hofbauer spotted a mistake in Lemma 22 of the published version. Lemma 22, Theorem 31, Corollaries 35 and 36 have to be fixed as follows:

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

Similarly, Theorem 22 should be rectified as follows:

- Let R and S be TRSs,
+ Let R be a non-duplicating TRS, S a TRS,

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