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.
Liste complète des métadonnées

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

http://hal.univ-grenoble-alpes.fr/hal-02549835
Contributeur : Thierry Boy de la Tour <>
Soumis le : mercredi 22 avril 2020 - 15:44:17
Dernière modification le : samedi 25 avril 2020 - 01:38:27

Fichier

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

Identifiants

  • HAL Id : hal-02549835, version 2

Collections

UGA | LIG | CNRS

Citation

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

Partager

Métriques

Consultations de la notice

14

Téléchargements de fichiers

17