On Semi-Completeness of Term Rewriting Systems
Bernhard Gramlich, 54 - Villers-les-Nancy (France). Unite de Recherche de Lorraine Institut National de Recherche en Informatique et en Automatique (INRIA) · 1997
: 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. Key-words: Theory of Computation, term rewriting, confluence, termination, semicompleteness. (R'esum'e : tsvp) This work was supported by a Marie Curie Research Fellowship of the European Community under contract No. ERBFMBICT961235. Unite de recherche INRIA Lorraine Technopole de Nancy-Brabois, Campus scientifique, 615 rue de Jardin Botanique, BP 101, 54600 VILLERS L ES NANCY (France) Telephone : (33) 83 59 30 30 -- Telecopie : (33) 83 27 83 19 Antenne de Metz, technopole de Metz 2000, 4...