On Semi-Completeness of Term Rewriting Systems
Résumé
We investigate the question whether semi-completeness, i.e., weak termination plus confluence, of term rewriting systems is preserved under the normalization of right-hand sides. We give a simple counterexample showing that in general this transformation neither preserves weak termination nor (local) confluence. Moreover we present two conditions which are sufficient for the preservation of semi-completeness. In particular, we show that (almost) orthogonal systems enjoy this preservation property.