Drags: an algebraic framework for graph rewriting

Authors: Nachum Dershowitz and Jean-Pierre Jouannaud

Paper Information

Title:Drags: an algebraic framework for graph rewriting
Authors:Nachum Dershowitz and Jean-Pierre Jouannaud
Proceedings:TERMGRAPH Pre-proceedings
Editors: Maribel Fernandez and Ian Mackie
Keywords:Term Rewriting, Graph rewriting, Multi-graphs, Cyclic graphs

ABSTRACT. Rewriting with graphs enjoys a long history in computer science, graphs being used to represent not only data structures, but also program structures, and even computational models. Termination and confluence techniques have been elaborated for various generalizations of trees, such as rational trees, directed acyclic graphs, lambda terms and lambda graphs. But the design of tools for rewriting arbitrary graphs has made little progress beyond various categorical definitions dating from the mid seventies and the study of the particular families of graphs listed above. This paper describes the generalization of term rewriting techniques to a general class of multigraphs that we call drags, viz. finite, directed, ordered (multi-)graphs. To this end, we develop a rich algebra of drags which allows us to view graph rewriting in exactly the same way as we view term rewriting.

Talk:Jul 07 11:00 (Session 26P: Frameworks)