Different strategies have been proposed for different classes of rewrite systems. Good strategies are sound, complete and efficient. These concepts are best understood when the term subject of a narrowing computation is an equation. Soundness means that narrowing computes only solutions of the equation. Completeness means that narrowing computes all the solutions of the equation.
Efficiency is more elusive.
A narrowing strategy computes a set of narrowing steps of a term. Every time a rule is used in a step, its variables are considered new. First, the substitution s is applied to the term t . Then, this subterm is replaced by the corresponding instance of r . The position is empty , i.e., the subterm to replace is the entire term.