A modular property of term rewriting systems is one that holds for the direct sum of two disjoint term rewriting systems iff it holds for every involved term rewriting system. A term rewriting system is r-consistent iff there is no term that can be rewritten to two different variables. We show that the subclass of left-linear and r-consistent term rewriting systems has the modular termination property. This subclass may also contain nonconfluent term rewriting systems. Since confluence implies r-consistency, this constitutes a generalisation of the theorem of Toyama, Klop, and Barendregt on the modularity of termination for confluent and left-linear term rewriting systems.
MODULAR TERMINATION OF R-CONSISTENT AND LEFT-LINEAR TERM REWRITING-SYSTEMS
MARCHIORI, MASSIMO;
1995
Abstract
A modular property of term rewriting systems is one that holds for the direct sum of two disjoint term rewriting systems iff it holds for every involved term rewriting system. A term rewriting system is r-consistent iff there is no term that can be rewritten to two different variables. We show that the subclass of left-linear and r-consistent term rewriting systems has the modular termination property. This subclass may also contain nonconfluent term rewriting systems. Since confluence implies r-consistency, this constitutes a generalisation of the theorem of Toyama, Klop, and Barendregt on the modularity of termination for confluent and left-linear term rewriting systems.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.