Rewriting on cyclic structures: Equivalence between the operational and the categorical description

DOI10.1051/ita:1999128zbMath0940.18002MaRDI QIDQ4943554

Andrea Corradini, Fabio Gadducci

Publication date: 11 May 2000

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/222074

zbMATH Keywords

term graph rewriting; algebraic 2-theories; automatic garbage collection; circular redexes; cyclic term graphs; folding/unfolding; sharing/unsharing

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68R10: Graph theory (including graph drawing) in computer science

68Q42: Grammars and rewriting systems

18C10: Theories (e.g., algebraic theories), structure, and semantics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hyperedge replacement jungle rewriting for term-rewriting systems and logic programming
• Petri nets are monoids
• On ``On graph rewritings
• On flowchart theories. II: The nondeterministic case
• Equational properties of iteration in algebraically complete categories
• Computation on graph-like expressions
• Optimal evaluations of graph-like expressions
• Speeding up subtree replacement systems
• Algebraic semantics
• Regular trees and the free iterative theory
• Conditional rewriting logic as a unified model of concurrency
• A general result on abstract flowchart schemes with applications to the study of accessibility, reduction and minimization
• On the algebraic structure of rooted trees
• Group axioms for iteration
• The equational logic of fixed points
• Axiomatizing schemes and their behaviors
• LEAN: An intermediate language based on graph rewriting
• Contextual nets
• An algebraic presentation of term graphs, via gs-monoidal categories
• REDEX CAPTURING IN TERM GRAPH REWRITING
• Implementing term rewriting by jungle evaluation
• FROM PETRI NETS TO LINEAR LOGIC THROUGH CATEGORIES: A SURVEY
• Structured Programming With and Without go to Statements
• Initial Algebra Semantics and Continuous Algebras
• A new implementation technique for applicative languages
• Minimal and Optimal Computations of Recursive Programs
• Traced monoidal categories