On 'On Graph Rewritings'

Research output: Contribution to journalArticle

40 Citations (Scopus)


In 1984, Raoult has given a description of graph rewriting. His description is operational, despite the similarity which his constructions have to the category-theoretic concept of a pushout. We describe a modification to Raoult's description of graph rewriting which allows the reduction of a redex to be described as a pushout, in a category of graphs where morphisms are not required to preserve graph structure.

Our description can also handle term rewrite rules whose right-hand sides consist of a variable. Raoult specifically excludes such rules from his treatment. Rules of this form include the K combinator, the identity function, selector functions for extracting components of data structures, and the conditional.

We prove the correctness of this implementation of term rewriting.
Original languageEnglish
Pages (from-to)37-58
Number of pages22
JournalTheoretical Computer Science
Issue number1-2
Publication statusPublished - 1987

Cite this