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: | 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. |
Pages: | 12 |
Talk: | Jul 07 11:00 (Session 26P: Frameworks) |
Paper: |