Universitšt Karlsruhe
Graph Rewrite Rules with Structural Recursion

Conference Article

[JHG:08]Berthold Hoffmann, Edgar Jakumeit, Rubino Geiß, Graph Rewrite Rules with Structural Recursion, GCM 2008, 2008.


Graph rewrite rules, programmed by sequencing and iteration, suffice to define the computable functions on graphs---in theory. In practice however, the control program may become hard to formulate, hard to understand, and even harder to verify. Therefore, we have extended graph rewrite rules by variables that are instantiated by a kind of hyperedge replacement, before the so instantiated rules are applied to a graph. This way, rules can be defined recursively over the structure of the graphs where they apply, in a fully declarative way. Generic rules with variables and recursive rule instantiation have been implemented in the graph rewrite tool GrGen.

[Generate bibTeX entry]




Dr. Rubino Geiß
Dr. Berthold Hoffmann
Former Students
Edgar Jakumeit