On graph rewriting, reduction, and evaluation in the presence of cycles

We inter-derive two prototypical styles of graph reduction: reduction machines à la Turner and graph rewriting systems à la Barendregt et al. To this end, we adapt Danvy et al.’s mechanical program derivations from the world of terms to the world of cyclic graphs. We also outline how to inter-derive...

Full description

Saved in:
Bibliographic Details
Published in:Higher-Order and Symbolic Computation 2013-12, Vol.26 (1-4), p.63-84
Main Author: Zerny, Ian
Format: Article
Language:English
Subjects:
Computational Intelligence
Computational Mathematics and Numerical Analysis
Computer Science
Mathematical Logic and Formal Languages
Symbolic and Algebraic Manipulation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We inter-derive two prototypical styles of graph reduction: reduction machines à la Turner and graph rewriting systems à la Barendregt et al. To this end, we adapt Danvy et al.’s mechanical program derivations from the world of terms to the world of cyclic graphs. We also outline how to inter-derive a third style of graph reduction: a graph evaluator.
ISSN:1388-3690
1573-0557
DOI:10.1007/s10990-014-9103-9