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)


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: 24 Jul 2024 08:46
URI: https://ueaeprints.uea.ac.uk/id/eprint/3721
DOI: 10.1016/0304-3975(87)90079-X

Actions (login required)

View Item View Item