On Parallel and Sequential Independence in Attributed Graph Rewriting - Université Grenoble Alpes Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2020

On Parallel and Sequential Independence in Attributed Graph Rewriting

Thierry Boy de La Tour
  • Fonction : Auteur
  • PersonId : 1022935

Résumé

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.
Fichier principal
Vignette du fichier
long-parindep.pdf (336.31 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02549835 , version 1 (21-04-2020)
hal-02549835 , version 2 (22-04-2020)
hal-02549835 , version 3 (03-06-2020)

Identifiants

  • HAL Id : hal-02549835 , version 1

Citer

Thierry Boy de La Tour. On Parallel and Sequential Independence in Attributed Graph Rewriting. 2020. ⟨hal-02549835v1⟩
69 Consultations
82 Téléchargements

Partager

Gmail Facebook X LinkedIn More