Completeness results for basic narrowing in non-copying implementations

Krishna Rao, M. R. K.

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Completeness results for basic narrowing in non-copying implementations

MPS-Authors

/persons/resource/persons44846

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

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

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: https://hdl.handle.net/11858/00-001M-0000-0014-ABC9-7

Abstract

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)