On ``On graph rewritings''
type: Item
instance of: scholarly article
title: On ``On graph rewritings''
zbMATH Open document ID: 0636.68028
DOI: 10.1016/0304-3975(87)90079-X
author: Richard Kennaway
published in: Theoretical Computer Science
publication date: 1987-01-01T00:00:00Z
review text: \textit{J. C. Raoult} [ibid. 32, 1-24 (1984; Zbl 0551.68065)] 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 fors model sheds light on why some instances of NP-complete problems are solvable in practice with a low average complexity.
Mathematics Subject Classification ID: 68Q65
Mathematics Subject Classification ID: 18B20
zbMATH DE Number: 4037181
zbMATH Keywords: rewrite as pushout in a category of graphs
zbMATH Keywords: graph rewriting
zbMATH Keywords: NP-complete problems
describes a project that uses: DACTL
MaRDI profile type: Publication
cites work: LEAN: An intermediate language based on graph rewriting
cites work: Q4692331
cites work: Q5639839
cites work: Q4692880
cites work: On graph rewritings
cites work: Computation on graph-like expressions
cites work: Optimal evaluations of graph-like expressions
cites work: Speeding up subtree replacement systems
full work available at URL: 0304-3975(87)90079-x
OpenAlex ID: W2130238476
description: scientific article; zbMATH DE number 4037181