The Journal of Functional and Logic Programming

Volume 1999

Article 1

Published by The MIT Press. Copyright 1999 Massachusetts Institute of Technology.

----------------------------------------------------------------

Your institution may already be a subscriber to JFLP. If not, please subscribe for legitimate access to all journal articles.

----------------------------------------------------------------

Meaningless Terms in Rewriting

Richard Kennaway, Vincent van Oostrom, and Fer-Jan de Vries

16 February 1999

Abstract

We present an axiomatic approach to the concept of meaninglessness in finite and transfinite term rewriting and lambda calculus We justify our axioms in several ways. They can be intuitively justified from the viewpoint of rewriting as computation. They are shown to imply important properties of meaninglessness: genericity of the class of meaningless terms, confluence modulo equality of meaningless terms, the consistency of equating all meaningless terms, and the construction of Böhm trees and models of rewrite systems. Finally, we show that they can be easily verified for many existing notions of meaninglessness and easily refuted for some notions that are known not to be good characterizations of meaninglessness.
The following versions of the article are available: You can find this article also on the ftp-server of The MIT Press (access may be faster from some sites).

----------------------------------------------------------------

Self citation

@article{jflp99-01,
author={Richard Kennaway and Vincent van Oostrom and Fer-Jan de Vries},
title={Meaningless Terms in Rewriting},
journal={Journal of Functional and Logic Programming},
volume={1999},
number={1},
publisher={The MIT Press},
month={February},
year={1999}
}

----------------------------------------------------------------

*back to* Main page