For narrowing to be an efficient evaluation mechanism, several
narrowing strategies have been proposed, although typically for the restricted case of left-linear constructor systems. These assumptions, while reasonable for functional programming applications, are too restrictive for a much broader range of applications to which narrowing can be fruitfully applied, including applications where rules have a non-equational meaning either as
in a concurrent system or as
in a logical system. In this paper, we propose an efficient lazy narrowing strategy called
which can be applied to general term rewriting systems with no restrictions whatsoever. An important consequence of this generalization is the
wide range of applications
that can now be efficiently supported by narrowing, such as symbolic model checking and theorem proving.