Set-theoretic graph rewriting

Abstract : Considering graphs as sets of vertices and arcs, we define their rewritings as simple set-theoretic rewritings : applying a rule consists of removing the left-hand side and adding the right-hand side. This point of view is explored through some instances. We show that these rewritings can simulate conventional graph rewritings, at least those which do not involve a quotient and term rewritings, at least those in which no left nor right-hand side is reduced to a variable. The simplicity of the approach is illustrated by a criterion of local confluence analogous to the well-known Knuth and Bendix criterion.
Type de document :
[Research Report] RR-1665, INRIA. 1992
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:49:12
Dernière modification le : vendredi 23 mars 2018 - 14:04:09
Document(s) archivé(s) le : mardi 12 avril 2011 - 19:56:47



  • HAL Id : inria-00074892, version 1


Jean-Claude Raoult, Frédéric Voisin. Set-theoretic graph rewriting. [Research Report] RR-1665, INRIA. 1992. 〈inria-00074892〉



Consultations de la notice


Téléchargements de fichiers