Home

A tutorial on graph transformation

A nice application of category theory to computer science that is rather simpler than its application to semantics tends to get is the single and double pushout approach to graph transformation. Categorical pushouts allow patterns and rewrites on many kinds of structure, in particular graphs, to be specified in a simple manner. The theory can be read forwards, generalising term rewriting systems to graph rewriting systems, or backwards, specifying parsing problems for a graph grammar.

There's a shortage of good introductory material to this idea online. Offline I can recommend Tutorial introduction to the algebraic approach of graph grammars based on double and single pushouts [citeseer]. Online I suggest Practical Use of Graph Rewriting, and I welcome other suggestions.

By Charles A Stewart at 2004-09-21 15:45 | Theory | other blogs | 16144 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Left adjoints preserve colimits; right adjoints, limits.

Here is another:
Wolfram Kahl. A Fibred Approach to Rewriting --- How the Duality between Adding and Deleting Cooperates with the Difference between Matching and Rewriting, TR 9702, Fakultät für Informatik, Universität der Bundeswehr München, 1997.

Also see Relational Methods in Computer Science and the very cool HOPS system.

By Frank Atanassow at Tue, 2004-09-21 17:53 | login or register to post comments

Simple?

When I say rather simpler than its application to semantics tends to get, I obviously didn't have in mind the "Application of the Grothendiek Construction" from Kahl's paper...

A nice set of links. A brief glance tells me that Kahl applies his papers to term graph rewriting, which I understand to mean that the graphs are DAGs. Do you know if the material generalises to cyclic graphs? I'm interested in Lamping -style graphs, which are essebntially cyclic.

By Charles A Stewart at Wed, 2004-09-22 05:34 | login or register to post comments

In vino veritas.

When I say rather simpler than its application to semantics tends to get, I obviously didn't have in mind the "Application of the Grothendiek Construction" from Kahl's paper...

Like the Yoneda lemma, the Grothendieck construction is really not as hard as it looks. It's just a way to relate two methods of indexing.

Do you know if the material generalises to cyclic graphs?

Dunno. I haven't read this stuff, though it looks interesting; it's perpetually on my reading list and so I thought I would post it here so you could give me your impressions. :)

As an educated guess, though, I would imagine that the theory works for general graphs, as they are more natural to treat from a categorical perspective than DAGs (since a category is a graph closed under a path-forming operation).

By Frank Atanassow at Thu, 2004-09-23 18:18 | login or register to post comments