On 'On Graph Rewritings'

Kennaway, J. Richard (1987) On 'On Graph Rewritings'. Theoretical Computer Science, 52 (1-2). pp. 37-58.

Full text not available from this repository. (Request a copy)

Abstract

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.

Item Type:	Article
Faculty \ School:	Faculty of Science > School of Computing Sciences
Depositing User:	EPrints Services
Date Deposited:	01 Oct 2010 13:42
Last Modified:	28 Mar 2025 05:09
URI:	https://ueaeprints.uea.ac.uk/id/eprint/3721
DOI:	10.1016/0304-3975(87)90079-X

Actions (login required)

View Item