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.