Subject: categories: graph term rewriting

From: "Bill Halchin" <[email-masked]>
Date: Mon, 04 Jun 2001 02:14:54

Hello,

   Research in graph term rewriting is being done
in regard to functional language implementation.
Have Category Theoretic methods been applied to
graph term rewriting research? If so, can someone
point me at papers?

Regards,

Bill Halchin

---

From: Konstantinos Tourlas <[email-masked]>
Date: Mon, 4 Jun 2001 11:03:12 +0100 (BST)

> graph term rewriting research? If so, can someone

To my best knowledge, Fabio Gadducci has, for some time now,
been applying category-theoretic structures to graph term rewriting,
and has written a couple of relevant survey papers which feature
extensive bibliographic references. I believe these papers may be
found in his home page (http://www.di.unipi.it/~gadducci/) even though
his links may seem a bit cryptic at first. 

My understanding of your question is that you're interested in
rewriting graphs which encode the structure of terms in some signature
(or the structure of program terms in some programming language). If,
instead, it is the rewriting of graphs (independent of specific
interpretations) or of programs in visual languages that you are
interested in, then I would be happy to provide more specific
pointers, as the latter area of research is closer to my own
interests.

-- 
Konstantinos Tourlas

Tel.   : 0131-650-5162 		Rm 1404, JCMB, The University of Edinburgh, 
e-mail : [email-masked]	King's Buildings, Edinburgh, EH9 3JZ UK

---

From: Frank Atanassow <[email-masked]>
Date: Mon, 4 Jun 2001 14:23:13 +0200

> graph term rewriting research? If so, can someone

You may wish to look at Wolfram Kahl's publications, and the HOPS project:

  http://ist.unibw-muenchen.de/kahl/

For example:

  Wolfram Kahl. A Fibred Approach to Rewriting - How the Duality between
    Adding and Deleting Cooperates with the Difference between Matching and
    Rewriting.  Technical Report Nr. 9702, Fakultät für Informatik,
    Universität der Bundeswehr München, May 1997.

Then there is Neil Ghani's work on categorical rewriting with Christopher
Lüth, though I don't think it is specific to graph rewriting:

  http://www.mcs.le.ac.uk/~nghani/catrew.html

And there is a lot of work on linear languages by Blute, Cockett, Seely et
al. which touches on rewriting. For example,

  Natural Deduction and Coherence for Weakly Distributive Categories
       (Blute-Cockett-Seely-Trimble) (JPAA 113(1996)3, pp 229-296)

which is available on Seely's page here:

  http://www.math.mcgill.ca/rags/

-- 
Frank Atanassow, Information & Computing Sciences, Utrecht University
Padualaan 14, PO Box 80.089, 3508 TB Utrecht, Netherlands
Tel +31 (030) 253-3261 Fax +31 (030) 251-379