vestal@SRC.Honeywell.COM (Steve Vestal) (10/17/90)
I would appreciate receiving any recent references for graph grammars, graph parsing, or graph rewriting, that anyone would care to email me. Steve Vestal Mail: Honeywell S&RC MN65-2100, 3660 Technology Drive, Minneapolis MN 55418 Phone: (612) 782-7049 Internet: vestal@src.honeywell.com
raoult@irisa.fr (Jean-Claude Raoult) (10/22/90)
There is a good number of articles (> 100) on the subject. Apart from ad hoc methods dating up from the sixties, here is a sample of more recent works: H. Ehrig: Introduction to the algebraic theory of graph grammars (a survey) in Graph Grammars and their Applications to Computer Science and Biology, LNCS 73 (1979). (A good introduction, particularly of the Berlin approach) J.C. Raoult: On graph rewriting, in TCS 32 (1984), and a better reformulation: R. Kennaway: On "On graph rewriting", in TCS 52 (1987). M. Loewe: Algebraic approach to graph transformation based on single push-out derivations, Techn. Rep. 90/5, T.U. Berlin (1990). A. Habel & H.-J. Kreowski: May we introduce to you Hyperedge replacement, in LNCS 291 (1987) G. Rozenberg: An introduction to the NLC way of rewriting graphs, in Graph grammars and their application to computer science, LNCS 291 (1987). (all these concerned with defining properly graph rewriting, all but the last making some reference to category theory) Uses of graph rewriting occur in several areas, e.g. P.Padawitz: Graph grammars and operational semantics, in TCS 19 (1982) H. Ehrig & B. Mahr: Fundamentals of algebraic specifications 1, Springer Berlin (1985). P. Degano & U. Montanari: A model of distributed system based on graph rewriting, in JACM 34(2) (1987). I. Litovski & Y. Metivier: Graph rewriting systems as a tool to design and to prove graph and network algorithms, Techn. Rep. 90-70, Universite de Bordeaux I (1990) (This is only a small part of existing applications. For instance I did not mention the applications to biology - cell development) Prof. Nagl has a huge listing of existing papers on the subject. Concerning parsing, things are worse because of the intrinsic complexities of graphs, compared with strings. You can have a taste at it with R. Franck: A class of linearly parsable graph grammars, in Acta Informatica 10 (1978). More generally, there is a relation between hyperedge replacement systems and (monadic second order) logic, yielding in some cases polynomial verification of graph properties. See for instance B. Courcelle: The monadic second order logic of graphs II: infinite graphs of bounded width, in Math. Systems Theory 21 (1989).