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.

Context-sensitive computations in functional and functional logic programs

Salvador Lucas

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)
• Source materials for custom formatting
  • 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)

You can find this article also on the ftp-server of The MIT Press (access may be faster from some sites).

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}
    }

Main page