[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