Infinitary Term Graph Rewriting

Details Infinitary Term Graph Rewriting Infinitary Term Graph Rewriting

2011-07-04

arxiv.org/abs/1107.0666v1

Computer Science

Logic in Computer Science

Scientific paper

Term graph rewriting provides a formalism for implementing term rewriting in an efficient manner by avoiding duplication. Infinitary term rewriting has been introduced to study infinite term reduction sequences. Such infinite reductions can be used to reason about lazy evaluation. In this paper, we combine term graph rewriting and infinitary term rewriting thereby addressing both components of lazy evaluation: non-strictness and sharing. Moreover, we show how our theoretical underpinnings, based on a metric space and a complete semilattice, provides a unified framework for both term rewriting and term graph rewriting. This makes it possible to study the correspondences between these two worlds. As an example, we show how the soundness of term graph rewriting w.r.t. term rewriting can be extended to the infinitary setting.

Affiliated with

Also associated with

No associations

Rating

Infinitary Term Graph Rewriting does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Infinitary Term Graph Rewriting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Infinitary Term Graph Rewriting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-4630