Granularity of conflicts and dependencies in graph transformation systems
- Conflict and dependency analysis (CDA) is a static analysis for the detection of conflicting and dependent rule applications in a graph transformation system. The state-of-the-art CDA technique, critical pair analysis, provides all potential conflicts and dependencies in minimal context as critical pairs, for each pair of rules. Yet, critical pairs can be hard to understand; users are mainly interested in core information about conflicts and dependencies occurring in various combinations. In this paper, we present an approach to conflicts and dependencies in graph transformation systems based on two dimensions of granularity. The first dimension refers to the overlap considered between the rules of a given rule pair; the second one refers to the represented amount of context information about transformations in which the conflicts occur. We introduce a variety of new conflict notions, in particular, conflict atoms, conflict reasons, and minimal conflict reasons, relate them to the existing conflict notions of critical pairs andConflict and dependency analysis (CDA) is a static analysis for the detection of conflicting and dependent rule applications in a graph transformation system. The state-of-the-art CDA technique, critical pair analysis, provides all potential conflicts and dependencies in minimal context as critical pairs, for each pair of rules. Yet, critical pairs can be hard to understand; users are mainly interested in core information about conflicts and dependencies occurring in various combinations. In this paper, we present an approach to conflicts and dependencies in graph transformation systems based on two dimensions of granularity. The first dimension refers to the overlap considered between the rules of a given rule pair; the second one refers to the represented amount of context information about transformations in which the conflicts occur. We introduce a variety of new conflict notions, in particular, conflict atoms, conflict reasons, and minimal conflict reasons, relate them to the existing conflict notions of critical pairs and initial conflicts, and position all of these notions within our granularity approach. Finally, we introduce dual concepts for dependency analysis. As we discuss in a running example, our approach paves the way for an improved CDA technique. (C) 2018 Elsevier Inc. All rights reserved.…
Author details: | Leen LambersORCiDGND, Kristopher Born, Jens KosiolORCiD, Daniel Strüber, Gabriele Taentzer |
---|---|
DOI: | https://doi.org/10.1016/j.jlamp.2018.11.004 |
ISSN: | 2352-2208 |
Title of parent work (English): | Journal of Logical and Algebraic Methods in Programming |
Subtitle (English): | a two-dimensional approach |
Publisher: | Elsevier |
Place of publishing: | New York |
Publication type: | Article |
Language: | English |
Date of first publication: | 2018/11/16 |
Publication year: | 2018 |
Release date: | 2021/04/15 |
Tag: | Critical pair analysis (CPA); Graph transformation (double pushout approach); Parallel independence |
Volume: | 103 |
Number of pages: | 25 |
First page: | 105 |
Last Page: | 129 |
Funding institution: | German Research FoundationGerman Research Foundation (DFG) [SPP 1593, 320336531]; research project Visual Privacy Management in User Centric |
Organizational units: | Digital Engineering Fakultät / Hasso-Plattner-Institut für Digital Engineering GmbH |
DDC classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke |
Peer review: | Referiert |