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 :
Rapport
[Research Report] RR-1665, INRIA. 1992
Liste complète des métadonnées

https://hal.inria.fr/inria-00074892
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:49:12
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
Document(s) archivé(s) le : mardi 12 avril 2011 - 19:56:47

Fichiers

Identifiants

  • HAL Id : inria-00074892, version 1

Citation

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

Partager

Métriques

Consultations de la notice

190

Téléchargements de fichiers

93