Accéder directement au contenu Accéder directement à la navigation
Pré-publication, Document de travail

On Parallel and Sequential Independence in Attributed Graph Rewriting

Abstract : We use graphs where vertices and arrows are attributed with sets of values, and rules that allow to delete data from a graph, to create new vertices or arrows, and to include values in attributes. Rules may be applied simultaneously, yielding a notion of parallelism that generalizes cellular automata in particular by allowing infinite matchings of rules in a graph. This is first used to define a notion of sequential independence of a set M of matchings of rules, even when M is infinite. Next, a notion of parallel independence of matchings is defined that accounts for the particular treatment of attributes, and it is proven that it characterizes sequential independence. Last, the effective deletion property, a condition that ensures that rules can be applied in parallel without conflicts, is proven to generalize parallel independence.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger

https://hal.univ-grenoble-alpes.fr/hal-02549835
Contributeur : Thierry Boy de la Tour <>
Soumis le : mercredi 3 juin 2020 - 14:41:02
Dernière modification le : vendredi 17 juillet 2020 - 11:10:23

Fichier

long-parindep-v3.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-02549835, version 3

Collections

LIG | CNRS | UGA

Citation

Thierry Boy de la Tour. On Parallel and Sequential Independence in Attributed Graph Rewriting. 2020. ⟨hal-02549835v3⟩

Partager

Métriques

Consultations de la notice

11

Téléchargements de fichiers

27