[Prev][Next][Index][Thread]
[pam@bu-cs.bu.edu: BU 4/26 colloq]
Date: Tue, 25 Apr 89 11:55:01 EST
From: pam@bu-cs.bu.edu
To: colloq@bu-cs.bu.edu
Subject: BU 4/26 colloq
BOSTON UNIVERSITY
Computer Science Dept.
111 Cummington St.
April 26, 1989
Redex Capturing in Term Graph Rewriting
Bill Farmer
The MITRE Corporation
Bedford, MA
Term graphs are a natural generalization of terms in which
structure sharing is allowed. Structure sharing makes term graph
rewriting a time- and space-efficient method for implementing term
rewrite systems. In term graph rewriting structure sharing schemes
can sometimes cause the left side of a rewrite rule to become a
subcomponent of the right side of the rule. This phenomenon, called
"redex capturing", introduces cycles into the term graph which is
being rewritten -- even when the graph and the rule themselves do not
contain cycles. In some applications redex capturing is undesirable,
such as in contexts where garbage collectors require that graphs be
acyclic. In other applications, for example in the use of the
fixed-point combinator Y, redex capturing acts as a rewriting
optimization. We show that in nearly all situations redex capturing
is sound in the sense that a finite term graph rewriting with redex
capturing corresponds to a certain infinite tree rewriting.
This is joint work with Ron Watro of The MITRE Corporation.
TIME: 4:00 PM
DATE: 4/26/89
PLACE: Room 135
Refreshments will be served 30 minutes prior to talk.
---pam