Natural narrowing for general term rewriting systems
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.
BibTeX
@inproceedings{conf/rta/EscobarMT05, author = "Escobar, Santiago and Meseguer, José and Thati, Prasanna", editor = "Giesl, Jürgen", title = "Natural Narrowing for General Term Rewriting Systems", booktitle = "RTA", crossref = "conf/rta/2005", ee = "http://dx.doi.org/10.1007/978-3-540-32033-3_21", keywords = "formal methods, programming languages", pages = "279-293", year = "2005", } @proceedings{conf/rta/2005, editor = "Giesl, Jürgen", title = "Term Rewriting and Applications, 16th International Conference, RTA 2005, Nara, Japan, April 19-21, 2005, Proceedings", isbn = "3-540-25596-6", publisher = "Springer", series = "Lecture Notes in Computer Science", volume = "3467", year = "2005", }