JFLP: Volume 1998, Article 1
The Journal of Functional and Logic Programming
Volume 1998
Article 1
Published by The MIT Press . Copyright 1998 Massachusetts Institute of Technology.
Your institution may already be a subscriber to JFLP. If not, please subscribe for legitimate access to all journal articles.
16 January 1998
Abstract
Context-sensitive rewriting is a refined form of rewriting that explores a smaller reduction space by imposing some fixed restrictions on the replacements. Any Term Rewriting System (TRS) can be given a context-sensitive rewrite relation. In this paper, we review the theory of context-sensitive rewriting and formulate conditions to guarantee the confluence of this relation. Also, for left-linear TRSs, we show that the (eventually obtained) computed value of a given expression can also be produced by context-sensitive rewriting, thus furnishing more efficient and still complete computations. We give the procedure for establishing the adequate replacement restrictions in order to achieve this. Finally, we raise the concept of context-sensitive restrictions from rewriting to narrowing, and provide the corresponding completeness results.The following versions of the article are available:
-
Preformatted versions of the article (compressed with
gzip
)- DVI (gzip'ped 92 kb)
- PostScript (gzip'ped 280 kb)
- PDF (gzip'ped 508 kb; uncompressed 710 kb)
-
LaTeX
(
JFLP-A98-01.tex
, gzip'ped 45 kb) -
BIBTeX
(
JFLP-A98-01.bib
, gzip'ped 3 kb) - Parameter settings for custom formatting ( cjropts.tex , 117 bytes)
Self citation
@article{jflp98-01, author={Salvador Lucas}, title={Context-sensitive computations in functional and functional logic programs}, journal={Journal of Functional and Logic Programming}, volume={1998}, number={1}, publisher={The MIT Press}, month={January}, year={1998} }