Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse




Conference Paper

Completeness results for basic narrowing in non-copying implementations


Krishna Rao,  M. R. K.
Programming Logics, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

Krishna Rao, M. R. K. (1996). Completeness results for basic narrowing in non-copying implementations. In M. Maher (Ed.), Logic Programming (pp. 393-407). Cambridge, USA: MIT Press.

Cite as:
Narrowing and rewriting play an important role in giving the operational semantics of languages that integrate functional and logic programming. These two operations are usually implemented using tree representation of terms and atoms. Such implementations do not allow sharing of similar structures. In contrast to this, implementations which use (directed acyclic) graph representations of terms and atoms allow sharing of similar structures. Such sharing saves space and avoids repetition of computations. Term graph rewriting is one of the nice models proposed in the literature to facilitate sharing of similar structures. In this paper, we study completeness of basic narrowing in term graph rewriting. Our results show that term graph rewriting not only improves efficiency but even facilitates more general results on the completeness of basic narrowing than the results known in term rewriting (which use tree representations)