×

Natural narrowing for general term rewriting systems. (English) Zbl 1078.68655

Giesl, Jürgen (ed.), Term rewriting and applications. 16th international conference, RTA 2005, Nara, Japan, April 19–21, 2005. Proceedings. Berlin: Springer (ISBN 3-540-25596-6/pbk). Lecture Notes in Computer Science 3467, 279-293 (2005).
Summary: 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.
For the entire collection see [Zbl 1070.68002].

MSC:

68Q42 Grammars and rewriting systems
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI