The Semantics and Pragmatics of Extended Term Graph Rewriting


Work Area: Logics and Logic Programming

Keywords term graph rewriting, graph rewriting, advanced compiler technology, abstract interpretation, abstract machines, parallel rewriting

Start Date: 1 July 92 / Duration: 36 months / Status: Starting

[ participants / contact ]

Abstract Todays software developer is faced with a range of programming paradigms embedded in increasingly sophisticated user interface standards. One way of attacking this complexity is to develop a computational model which is intermediate between low machine level models, the models associated with particular programming paradigms, and the higher level interface models. Semagraph II continues the work of Semagraph I, by exploring the potential of a term graph rewriting model of computation. Of specific interest is the theory of orthogonal term rewrite systems and its relation to term graph rewriting. Topics studied include type systems for term graphs, modularity, notions of simulation, practical extensions of term graph rewriting, and control issues.


The long-term objective of Semagraph partners is to develop a comprehensive practical theory for reasoning about the performance and functionality of IT systems which is based on term graphs as opposed to trees . A key short term aim of this working group is to consolidate and promulgate results from the Semagraph I (BRA 3074) project, both theoretical and practical.


The group concentrates on extending the theory of orthogonal term graph rewriting, and relating it to experience obtained with the partners' prototype implementations. The following topics indicate the scope of the working group: foundations of term graph rewriting, appropriate notions of typing, modularity, and simulation for term graphs; the relationship between term graph rewriting and other notions of graph transformation; extensions of term graph rewriting to support control and limited notions of state, mapping of process calculi to extended term graph models, semantic-based transformation techniques for deriving control information automatically.

Nijmegen's Concurrent CLEAN programming system, which is based on term graph rewriting and runs on several industry standard platforms, was exhibited at the CeBit'93 fair, attracting some serious industrial interest. Representatives of COMPUGRAPH attended the Semagraph'93 workshop.

Two new promising areas of activity are:

Progress and Results

Much of the first year of Semagraph II was occupied by the publication of major results in book form. This has resulted in two books appearing during 1993. On the practical side, Nijmegen continues to release improved versions of the Concurrent CLEAN programming system.


Future systems will increasingly be designed using several language paradigms. Extended term graph models of computation provide a good candidate of a common model of computation both for reasoning about functionality and performance of hybrid systems.

Latest Publications

Information Dissemination Activies

Two books describing the practical and theoretical results obtained so far have been published, and practical work exhibited at the CeBit'93 fair.


University of East Anglia - UK
School of Information Systems


Université de Rennes - F
Katholieke Univeristeit Nijmegen - NL
Centrum voor Wiskunde en Informatica - NL
The Imperial College of Science, Technology and Medicine - UK


Prof. M.R. Sleep
tel +44/603 592693
fax +44/603 507720

LTR synopses home page LTR work area index LTR acronym index LTR number index LTR Working Groups index
All synopses home page all acronyms index all numbers index

SEMAGRAPH II - 6345, August 1994

please address enquiries to the ESPRIT Information Desk

html version of synopsis by Nick Cook