On Simultaneous Transformations with Overlapping Graph Rewrite Systems

Abstract : We tackle the problem of simultaneous transformations of networks represented as graphs. Roughly speaking, one may distinguish two kinds of simultaneous or parallel rewrite relations over complex structures such as graphs: (i) those which transform disjoint subgraphs in parallel and hence can be simulated by successive mere sequential and local transformations and (ii) those which transform overlapping subgraphs simultaneously. In the latter situations, parallel transformations cannot be simulated in general by means of successive local rewrite steps. We investigate this last problem in the framework of overlapping graph transformation systems. As parallel transformation of a graph does not produce a graph in general, we propose first some sufficient conditions that ensure the closure of graphs by parallel rewrite relations. Then we mainly introduce and discuss two parallel rewrite relations over graphs. One relation is functional and thus deterministic, the other one is not functional for which we propose sufficient conditions which ensure its confluence.
Type de document :
Communication dans un congrès
LPAR-21, 21th International Conference on Logic for Programming, Artificial Intelligence and Reasoning, May 2017, Maun, Botswana. pp.300-318, 〈http://www.easychair.org/publications/paper/340362〉
Liste complète des métadonnées

http://hal.univ-grenoble-alpes.fr/hal-01633398
Contributeur : Aude Maignan <>
Soumis le : dimanche 12 novembre 2017 - 19:03:59
Dernière modification le : jeudi 11 janvier 2018 - 06:26:19

Identifiants

  • HAL Id : hal-01633398, version 1

Collections

Citation

Rachid Echahed, Aude Maignan. On Simultaneous Transformations with Overlapping Graph Rewrite Systems. LPAR-21, 21th International Conference on Logic for Programming, Artificial Intelligence and Reasoning, May 2017, Maun, Botswana. pp.300-318, 〈http://www.easychair.org/publications/paper/340362〉. 〈hal-01633398〉

Partager

Métriques

Consultations de la notice

55