## A Parallel Narrowing Strategy

**Sergio Antoy and Rachid Echahed and Michael Hanus**
*Technical Report TR 96-1, Portland State University, 1996*

We generalize to narrowing the notion of necessary set of redexes
proposed by Sekar and Ramakrishnan for rewriting in weakly orthogonal,
constructor-based rewrite systems.
We define two strategies, one sequential and the other parallel,
based on this notion. Both strategies are sound and complete.
The parallel strategy is a conservative extensions of
two optimal strategies. When applied to
inductively sequential rewrite systems, it behaves as needed
narrowing and when applied to ground terms it behaves as Sekar and
Ramakrishnan rewriting strategy.

Available:
PDF
BibTeX-Entry

Note: An implementation of this strategy is available
here.

Michael Hanus