# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### A Needed Narrowing Strategy

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Antoy, S., Echahed, R., & Hanus, M. (1994). A Needed Narrowing Strategy. In *Proceedings of the 21st ACM Symposium on Principles of Programming Languages (POPL'94)* (pp. 268-279).
New York, USA: ACM.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-AD59-4

##### 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.