Dominique
Duval
Graph rewriting
In the double pushout approach for graph
rewriting, a rewrite
rule is a pair of graph homomorphisms of the form L<--K--> R.
Usually K is a kind of intersection of the left handside L and the
righthandside R, and the homomorphism from K to
L is a monomorphism. On the contrary, we
consider that K stands for a version of L where some vertices are
disconnected, and the homomorphism
from K to L is an epimorphism. This provides a
framework for dealing with the problem of
data-structure rewriting including pointer
redirections
[Duval-Echahed-Prost
2006].
In addition, the categorical point
of view can also be used for dealing with garbage
collection. Indeed, garbage
collection is easily defined as a right adjoint, that can be expressed
as composed of a left adjoint and two "easy"
right adjoints. These three adjoints cope
well with the different phases of a traditional garbage
collector. Since left
adjoints preserve pushouts, this decomposition is compatible with the
double pushout approach for graph rewriting
[Duval-Echahed-Prost
2007]. See [Yegdjong08] for an implementation.
In [Duval-Echahed-Prost
2009] we propose a new framework for
performing local and global redirection of pointers, addition and
deletion of nodes as well as cloning and collapsing of substructures.
For this purpose, we introduce a notion of
heterogeneous pushout and define rewrite steps as heterogeneous
pushouts in a given category. See [Mavillaz09]
for an implementation.
[Mavillaz09] Daniel
Mavillaz. Méthodes
algébriques
pour la transformation de graphes. Rapport de stage
(Grenoble 2009).
[Yegdjong08] Elias Yegdjong. Conception
et réalisation d'une interface graphique pour la
réécriture de l'état d'une mémoire
d'ordinateur. Rapport de stage (Grenoble 2008). Présentation.
[Duval-Echahed-Prost 2009] Dominique Duval, Rachid Echahed, Frédéric Prost. A Heterogeneous Pushout Approach to Term-Graph Transformation. Proceedings of Rewriting Techniques and Application 2009 (RTA'09). Springer Lecture Notes in Computer Science 5595 p. 194-208 (2009).
[Duval-Echahed-Prost 2007]
Dominique Duval, Rachid Echahed, Frédéric
Prost. Adjunction
for Garbage Collection with Application to Graph Rewriting.
Proceedings of Rewriting Techniques and Application 2007 (RTA'07).
Springer Lecture Notes in Computer
Science 4533 p. 122-136 (2007).
[Duval-Echahed-Prost 2006] Dominique Duval, Rachid Echahed,
Frédéric
Prost.
Modeling
pointer redirection
as cyclic term-graph rewriting. In Proceedings of the Third
International Workshop on Term Graph Rewriting (TERMGRAPH'06). Electronic
Notes in Computer Science 176 p. 65-84
(2007).