Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Chapitre d'ouvrage

Parallel Coherent Graph Transformations

Abstract : Cellular automata as well as simultaneous assignments in Python can be understood as the parallel application of local rules to a grid or an environment that can be easily represented as an attributed graph. Since the result of such transformations cannot generally be obtained by a sequential application of the involved rules, this situation infringes the standard notion of parallel independence. An algebraic approach with production rules of the form L←K←I→R is adopted and a condition of parallel coherence more general than parallel independence is formulated, that enable the definition of the Parallel Coherent Transformation (PCT). This transformation supports a generalisation of the Parallelism Theorem in the theory of adhesive HLR categories, showing that the PCT yields the expected result of sequential rewriting steps when parallel independence holds. Categories of finitely attributed structures are proposed, in which PCTs are guaranteed to exist. These notions are introduced and illustrated on several detailed examples.
Type de document :
Chapitre d'ouvrage
Liste complète des métadonnées

https://hal.univ-grenoble-alpes.fr/hal-03430231
Contributeur : Thierry Boy de la Tour Connectez-vous pour contacter le contributeur
Soumis le : mardi 16 novembre 2021 - 10:24:31
Dernière modification le : dimanche 20 février 2022 - 12:38:04
Archivage à long terme le : : jeudi 17 février 2022 - 18:20:54

Fichier

pct-final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Thierry Boy de la Tour, Rachid Echahed. Parallel Coherent Graph Transformations. Markus Roggenbach. Recent Trends in Algebraic Development Techniques, 12669, Springer International Publishing, pp.75-97, 2021, Lecture Notes in Computer Science, 978-3-030-73784-9. ⟨10.1007/978-3-030-73785-6_5⟩. ⟨hal-03430231⟩

Partager

Métriques

Consultations de la notice

13

Téléchargements de fichiers

20