@INPROCEEDINGS{AntoyEchahedHanus93Report,
AUTHOR = {Antoy, S. and Echahed, R. and Hanus, M.},
TITLE = {A Needed Narrowing Strategy},
YEAR = {1993},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik, Saarbr{\"u}cken},
NUMBER = {MPI-I-93-243},
TYPE = {Technical Report},
NOTE = {Short version in Proc.~of the 21st ACM Symposium on Principles of Programming Languages},
ABSTRACT = {Narrowing is the operational principle of languages that
integrate functional and logic programming. We propose
a notion of a needed narrowing step that, for inductively
sequential rewrite systems, extends the Huet and Levy notion
of a needed reduction step. We define a strategy, based
on this notion, that computes only needed narrowing steps.
Our strategy is sound and complete for a large class of
rewrite systems, is optimal w.r.t. the cost measure that
counts the number of distinct steps of a derivation, computes
only independent unifiers, and is efficiently implemented
by pattern matching.},
}