Set-theoretic graph rewriting
Résumé
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.