[Prev][Next][Index][Thread]

New book on TERM GRAPH REWRITING


TERM GRAPH REWRITING: theory and practice
-----------------------------------------
eds M.R.Sleep, M.J.Plasmeijer and M.C.J.D. van Eekelen

John Wiley, April 1993. Price approx. 47.95 USD, 29.95 LUK.


TERM GRAPH REWRITING refers to techniques and theories for
representing terms and term rewrite rules as graphs and graph rewrite
rules. Many modern programming paradigms - most notably the functional
and logic paradigms - have term rewriting at their heart, although the
control regimes and semantics are very different. Practical
implementations of these languages share subterms using pointers, and
the machine code for such programs manipulates shared structures
(called in this volume {\em term graphs}).

The operational semantics of the resulting programs may be represented
as a set of term graph rewriting rules. Reasoning about the
correctness and efficiency of such representations relies on our
ability to reason about term graph rewriting systems, and to relate
them to other semantic models.  Used in this way, term graph rewriting
offers a model of computation which is closer to real implementations
than pure term rewriting, but which avoids unnecessary machine detail.

Graph rewriting was the focus of a number of European ESPRIT Basic
Research Actions most notably SEMAGRAPH and COMPUGRAPH. Both projects
led to theoretical and practical advances for term graph rewriting
reflecting the state of the art, and these form the contents of this
book.

CONTENTS
--------

An Introduction to Term Graph Rewriting 
J.R.~Kennaway, J.W.~Klop, M.R.~Sleep, and F.J.~de~Vries

Partial Type Assignment in Left Linear Applicative Term Rewriting Systems 
S.~van~Bakel, S.~Smetsers, and S.~Brock 

How to Get Confluence for Explicit Substitutions 
T.~Hardin 

An Infinitary Church-Rosser Property for Non-collapsing Orthogonal 
Term Rewriting Systems 
J.R.~Kennaway, J.W.~Klop, M.R.~Sleep, and F.J.~de~Vries 

The Functional Strategy and Transitive Term Rewriting Systems 
Y.~Toyama, S.~Smetsers, M.~van~Eekelen and R.~Plasmeijer 

Graph Rewriting Systems for Efficient Compilation 
Z.M.~Ariola and Arvind 

A Fibration Semantics for Externded Term Graph Rewriting 
R.~Banach 

A New Term Graph Rewriting Formalism: Hyperedge Replacement Jungle 
Rewriting 
A.~Corradini and F.~Rossi

Abstract Reduction: Towards a Theory via Abstract Interpretation 
M.~van~Eekelen, E.~Goubault, C.~Hankin and E.~N\"ocker 

A Lattice for the Abstract Interpretation of Term Graph Rewriting Systems 
E.~Goubault and C.~Hankin 

Event Structures and Orthogonal Term Graph Rewriting 
J.R.~Kennaway, J.W.~Klop, M.R.~Sleep, and F.J.~de~Vries 

The Adequacy of Term Graph Rewriting for Simulating Term Rewriting 
J.R.~Kennaway, J.W.~Klop, M.R.~Sleep, and F.J.~de~Vries 

Translations into the Graph Grammar Machine 
H-J.~Kreowski 

An Algebraic Framework for the Transformation of Attributed Graphs 
M.~Lowe, M.~Korff and A.~Wagner 

Hypergraph Rewriting: Critical Pairs and Undecidability of Confluence 
D.~Plump 

A Quick Look at Tree Transductions 
J.C.~Raoult 

Paragon Specifications and Their Implementations 
P.~Anderson, D.~Bolton and P.~Kelly 

MONSTR: Term Graph Rewriting for Parallel Machines 
R.~Banach 

A Graph Rewriting Model Enhanced with Sharing for OR-parallel Execution 
of Logic Programs 
W.~Damm, F.~Lui and T.~Peikenkamp 

A New Process Model for Functions 
J.~Glauert, L.~Leth and B.~Thomsen 

Parallel Execution of Concurrent Clean on ZAPP 
R.~Goldsmith, D.L.~McBurney and M.R.~Sleep 

Graph-based Operational Semantics of a Lazy Functional Language 
Kristoffer H.~Rose 

Graph Rewritng Using the Annotated Functional Strategy 
P.~Koopman, S.~Smetsers,  M.~van~Eekelen and R.~Plasmeijer 

Implementing Logical Variables and Disjunctions in Graph Rewrite Systems 
P.~McBrien 

Process Annotations and Process Types 
R.~Plasmeijer and M.~van~Eekelen 

JALPA: A Functional Modular Programming Language Based on Extended
Graphical Term Rewriting 
H.~Yamanaka