by Kristopher Born, Leen Lambers, Daniel Strüber, Gabriele Taentzer
Abstract:
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 its users the benefits of completeness i.e. its output contains a precise representation of each potential conflict and dependency in a minimal context called critical pair. Yet user feedback has shown that critical pairs can be hard to understand; users are interested in core information ab out conflicts and dependencies occurring in various combinations. In this paper we investigate the granularity of conflicts and dependencies in graph transformation systems. We introduce a variety of new concepts on different granularity levels: We start with conflict atoms representing individual graph elements as smallest building bricks that may cause a conflict. We show that each conflict atom can b e extended to at least one conflict reason and conversely each conflict reason is covered by atoms. Moreover we relate conflict atoms to minimal conflict reasons representing smallest element sets to b e overlapped in order to obtain a pair of conflicting transformations. We show how conflict reasons are related to critical pairs. Finally we introduce dual concepts for dependency analysis. As we discuss in a running example our concepts pave the way for an improved CDA technique.
Reference:
Granularity of Conflicts and Dependencies in Graph Transformation Systems (Kristopher Born, Leen Lambers, Daniel Strüber, Gabriele Taentzer), In International Conference on Graph Transformation (ICGT) (Juan de Lara, Detlef Plump, eds.), Springer International Publishing, 2017. (Extended version: https://www.uni-marburg.de/fb12/arbeitsgruppen/swt/forschung/publikationen/2017/BLST17-EV.pdf)
Bibtex Entry:
@InProceedings{BLST17,
AUTHOR = {Born, Kristopher and Lambers, Leen and Strüber, Daniel and Taentzer, Gabriele},
TITLE = {{Granularity of Conflicts and Dependencies in Graph Transformation Systems}},
YEAR = {2017},
BOOKTITLE = {International Conference on Graph Transformation (ICGT)},
PAGES = {125-141},
EDITOR = {de Lara, Juan and Plump, Detlef},
SERIES = {Lecture Notes in Computer Science},
PUBLISHER = {Springer International Publishing},
URL = {https://link.springer.com/content/pdf/10.1007%2F978-3-319-61470-0_8.pdf},
PDF = {uploads/pdf/BLST17_978-3-319-61470-0_8.pdf},
OPTacc_pdf = {},
ABSTRACT = {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 its users the benefits of completeness i.e. its output contains a precise representation of each potential conflict and dependency in a minimal context called critical pair. Yet user feedback has shown that critical pairs can be hard to understand; users are interested in core information ab out conflicts and dependencies occurring in various combinations. In this paper we investigate the granularity of conflicts and dependencies in graph transformation systems. We introduce a variety of new concepts on different granularity levels: We start with conflict atoms representing individual graph elements as smallest building bricks that may cause a conflict. We show that each conflict atom can b e extended to at least one conflict reason and conversely each conflict reason is covered by atoms. Moreover we relate conflict atoms to minimal conflict reasons representing smallest element sets to b e overlapped in order to obtain a pair of conflicting transformations. We show how conflict reasons are related to critical pairs. Finally we introduce dual concepts for dependency analysis. As we discuss in a running example our concepts pave the way for an improved CDA technique.},
NOTE = {Extended version: https://www.uni-marburg.de/fb12/arbeitsgruppen/swt/forschung/publikationen/2017/BLST17-EV.pdf}
}