## Files in this item

FilesDescriptionFormat

application/pdf

UIUCDCS-R-2009-3049.pdf (312kB)
(no description provided)PDF

## Description

 Title: Variant Narrowing and Extreme Termination Author(s): Escobar, Santiago; Meseguer, José; Sasse, Ralf Subject(s): Computer Science Abstract: For narrowing with a set of rules \Delta modulo a set of axioms B almost nothing is known about terminating narrowing strategies, and basic narrowing is known to be incomplete for B=AC. In this work we ask and answer the question: Is there such a thing as an extremely terminating narrowing strategy modulo B? where we call a narrowing strategy S enjoying appropriate completeness properties extremely terminating iff whenever any other narrowing strategy S' enjoying the same completeness properties terminates on a term t, then S is guaranteed to terminate on t as well. We show that basic narrowing is not extremely terminating already for B=\emptyset, and provide a positive answer to the above question by means of a sequence of increasingly more restrictive variant narrowing strategies, called variant narrowing, variant narrowing with history, \Delta,B--pattern narrowing with history, and \Delta,B--pattern narrowing with history and folding, such that given a set \Delta of confluent, terminating, and coherent rules modulo B: (i) \Delta,B--pattern narrowing with history (and folding) are strictly more restrictive than basic narrowing; (ii) \Delta,B--pattern narrowing with history and folding is an extremely terminating strategy modulo B, which terminates on a term t iff t has a finite, complete set of minimal variants; (iii) \Delta,B--pattern narrowing with history and folding terminates on all terms iff \Delta \cup B has the finite variant property; and (iv) \Delta,B--pattern narrowing with history and folding yields a complete and minimal \Delta \cup B-unification algorithm, which is finitary when \Delta \cup B has the finite variant property. Issue Date: 2009-03 Type: Text URI: http://hdl.handle.net/2142/10848 Date Available in IDEALS: 2009-04-15
﻿