2005 | OriginalPaper | Buchkapitel
Natural Narrowing for General Term Rewriting Systems
verfasst von : Santiago Escobar, José Meseguer, Prasanna Thati
Erschienen in: Term Rewriting and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
For narrowing to be an efficient evaluation mechanism, several
lazy
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
transitions
in a concurrent system or as
inferences
in a logical system. In this paper, we propose an efficient lazy narrowing strategy called
natural narrowing
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.