Adhesive subcategories of functor categories with instantiation to partial triple graphs. (English) Zbl 1429.68089
Guerra, Esther (ed.) et al., Graph transformation. 12th international conference, ICGT 2019, held as part of STAF 2019, Eindhoven, the Netherlands, July 15–16, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11629, 38-54 (2019).
Summary: Synchronization and integration processes of correlated models that are formally based on triple graph grammars often suffer from the fact that elements are unnecessarily deleted and recreated losing information in the process. It has been shown that this undesirable loss of information can be softened by allowing partial correspondence morphisms in triple graphs. We provide a formal framework for this new synchronization process by introducing the category \(\mathbf{PTrG}\) of partial triple graphs and proving it to be adhesive. This allows for ordinary double pushout rewriting of partial triple graphs. To exhibit \(\mathbf{PTrG}\) as an adhesive category, we present a fundamental construction of subcategories of functor categories and show that these are adhesive HLR if the base category already is. Secondly, we consider an instantiation of this framework by triple graphs to illustrate its practical relevance and to have a concrete example at hand.
For the entire collection see [Zbl 1428.68021].
For the entire collection see [Zbl 1428.68021].
MSC:
| 68Q42 | Grammars and rewriting systems |
| 18A25 | Functor categories, comma categories |
| 18A30 | Limits and colimits (products, sums, directed limits, pushouts, fiber products, equalizers, kernels, ends and coends, etc.) |
| 18A35 | Categories admitting limits (complete categories), functors preserving limits, completions |
References:
| [1] | Abou-Saleh, F.; Cheney, J.; Gibbons, J.; McKinna, J.; Stevens, P.; Gibbons, J.; Stevens, P., Introduction to bidirectional transformations, Bidirectional Transformations, 1-28, 2018, Cham: Springer, Cham · Zbl 1476.68034 · doi:10.1007/978-3-319-79108-1_1 |
| [2] | Awodey, S., Category Theory, Oxford Logic Guides, 2010, New York: Oxford University Press Inc., New York · Zbl 1194.18001 |
| [3] | Czarnecki, K.; Foster, JN; Hu, Z.; Lämmel, R.; Schürr, A.; Terwilliger, JF; Paige, RF, Bidirectional transformations: a cross-discipline perspective, Theory and Practice of Model Transformations, 260-283, 2009, Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-02408-5_19 |
| [4] | Ehrig, H.; Heckel, R.; Korff, M.; Löwe, M.; Ribeiro, L.; Wagner, A.; Corradini, A., ALGEBRAIC APPROACHES TO GRAPH TRANSFORMATION - PART II: SINGLE PUSHOUT APPROACH AND COMPARISON WITH DOUBLE PUSHOUT APPROACH, Handbook of Graph Grammars and Computing by Graph Transformation, 247-312, 1997 · doi:10.1142/9789812384720_0004 |
| [5] | Ehrig, H., Ehrig, K., Prange, U., Taentzer, G.: Fundamentals of Algebraic Graph Transformation. Monographs in Theoretical Computer Science, Springer, Heidelberg (2006). doi:10.1007/3-540-31188-2 · Zbl 1095.68047 |
| [6] | Ehrig, H.; Orejas, F.; Prange, U.; Corradini, A.; Ehrig, H.; Montanari, U.; Ribeiro, L.; Rozenberg, G., Categorical foundations of distributed graph transformation, Graph Transformations, 215-229, 2006, Heidelberg: Springer, Heidelberg · Zbl 1157.68039 · doi:10.1007/11841883_16 |
| [7] | Fritsche, L.; Kosiol, J.; Schürr, A.; Taentzer, G.; Hähnle, R.; van der Aalst, W., Efficient model synchronization by automatically constructed repair processes, Fundamental Approaches to Software Engineering, 116-133, 2019, Cham: Springer, Cham · doi:10.1007/978-3-030-16722-6_7 |
| [8] | Fritsche, L.; Kosiol, J.; Schürr, A.; Taentzer, G.; Mazzara, M.; Ober, I.; Salaün, G., Short-cut rules. Sequential composition of rules avoiding unnecessary deletions, Software Technologies: Applications and Foundations, 415-430, 2018, Cham: Springer, Cham · doi:10.1007/978-3-030-04771-9_30 |
| [9] | Giese, H., Hildebrandt, S.: Efficient model synchronization of large-scale models. Technical report 28, Hasso-Plattner-Institut (2009) |
| [10] | Giese, H.; Wagner, R., From model transformation to incremental bidirectional model synchronization, Softw. Syst. Modeling, 8, 1, 21-43, 2009 · doi:10.1007/s10270-008-0089-9 |
| [11] | Golas, U.; Lambers, L.; Ehrig, H.; Giese, H.; Ehrig, H.; Engels, G.; Kreowski, H-J; Rozenberg, G., Toward bridging the gap between formal foundations and current practice for triple graph grammars, Graph Transformations, 141-155, 2012, Heidelberg: Springer, Heidelberg · Zbl 1367.68134 · doi:10.1007/978-3-642-33654-6_10 |
| [12] | Greenyer, J.; Pook, S.; Rieke, J.; France, RB; Kuester, JM; Bordbar, B.; Paige, RF, Preventing information loss in incremental model synchronization by reusing elements, Modelling Foundations and Applications, 144-159, 2011, Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-21470-7_11 |
| [13] | Habel, A.; Pennemann, KH, Correctness of high-level transformation systems relative to nested conditions, Math. Struct. Comput. Sci., 19, 245-296, 2009 · Zbl 1168.68022 · doi:10.1017/S0960129508007202 |
| [14] | Hayman, J.; Heindel, T.; Giese, H.; König, B., On pushouts of partial maps, Graph Transformation, 177-191, 2014, Cham: Springer, Cham · Zbl 1425.68163 · doi:10.1007/978-3-319-09108-2_12 |
| [15] | Heindel, T.; Ehrig, H.; Rensink, A.; Rozenberg, G.; Schürr, A., Hereditary pushouts reconsidered, Graph Transformations, 250-265, 2010, Heidelberg: Springer, Heidelberg · Zbl 1306.68073 · doi:10.1007/978-3-642-15928-2_17 |
| [16] | Hermann, F., Model synchronization based on triple graph grammars: correctness, completeness and invertibility, Softw. Syst. Modeling, 14, 1, 241-269, 2015 · doi:10.1007/s10270-012-0309-1 |
| [17] | Kastenberg, H.; Rensink, A.; Heckel, R.; Taentzer, G., Graph attribution through sub-graphs, Graph Transformation, Specifications, and Nets, 245-265, 2018, Cham: Springer, Cham · Zbl 1383.68063 · doi:10.1007/978-3-319-75396-6_14 |
| [18] | Kennaway, R.; Ehrig, H.; Kreowski, H-J; Rozenberg, G., Graph rewriting in some categories of partial morphisms, Graph Grammars and Their Application to Computer Science, 490-504, 1991, Heidelberg: Springer, Heidelberg · Zbl 0765.68065 · doi:10.1007/BFb0017408 |
| [19] | König, H.; Diskin, Z.; Anjorin, A.; Espinoza, H., Efficient consistency checking of interrelated models, Modelling Foundations and Applications, 161-178, 2017, Cham: Springer, Cham · doi:10.1007/978-3-319-61482-3_10 |
| [20] | Kosiol, J., Fritsche, L., Schürr, A., Taentzer, G.: Adhesive subcategories of functor categories with instantiation to partial triple graphs: extended version. Technical report, Philipps-Universität Marburg (2019). https://cms.uni-marburg.de/fb12/arbeitsgruppen/swt/forschung/publikationen/2019/KFST19-TR.pdf/download |
| [21] | Lack, S.; Sobociński, P., Adhesive and quasiadhesive categories, Theoret. Inform. Appl., 39, 3, 511-545, 2005 · Zbl 1078.18010 · doi:10.1051/ita:2005028 |
| [22] | Lauder, M.; Anjorin, A.; Varró, G.; Schürr, A.; Ehrig, H.; Engels, G.; Kreowski, H-J; Rozenberg, G., Efficient model synchronization with precedence triple graph grammars, Graph Transformations, 401-415, 2012, Heidelberg: Springer, Heidelberg · Zbl 1367.68143 · doi:10.1007/978-3-642-33654-6_27 |
| [23] | Löwe, M., Algebraic approach to single-pushout graph transformation, Theoret. Comput. Sci., 109, 1, 181-224, 1993 · Zbl 0787.18001 · doi:10.1016/0304-3975(93)90068-5 |
| [24] | Machado, R.; Ribeiro, L.; Heckel, R., Rule-based transformation of graph rewriting rules: towards higher-order graph grammars, Theoret. Comput. Sci., 594, 1-23, 2015 · Zbl 1328.68103 · doi:10.1016/j.tcs.2015.01.034 |
| [25] | Montanari, U.; Ribeiro, L.; Corradini, A.; Ehrig, H.; Kreowski, H-J; Rozenberg, G., Linear ordered graph grammars and their algebraic foundations, Graph Transformation, 317-333, 2002, Heidelberg: Springer, Heidelberg · Zbl 1028.68074 · doi:10.1007/3-540-45832-8_24 |
| [26] | Orejas, F., Lambers, L.: Symbolic attributed graphs for attributed graph transformation. Electronic Communications of the EASST, vol. 30. (International Colloquium on Graph and Model Transformation (GraMoT) 2010) (2010) |
| [27] | Robinson, E.; Rosolini, G., Categories of partial maps, Inf. Comput., 79, 2, 95-130, 1988 · Zbl 0656.18001 · doi:10.1016/0890-5401(88)90034-X |
| [28] | Schürr, A.; Mayr, EW; Schmidt, G.; Tinhofer, G., Specification of graph translators with triple graph grammars, Graph-Theoretic Concepts in Computer Science, 151-163, 1995, Heidelberg: Springer, Heidelberg · Zbl 1528.68166 · doi:10.1007/3-540-59071-4_45 |
| [29] | Shir Ali Nasab, A.R., Hosseini, S.N.: Pullback in partial morphism categories. Appl. Categorical Struct. 25(2), 197-225 (2017) · Zbl 1397.18006 |
| [30] | Stünkel, P., König, H., Lamo, Y., Rutle, A.: Multimodel correspondence through inter-model constraints. In: Conference Companion of the 2nd International Conference on Art, Science, and Engineering of Programming, pp. 9-17. ACM, New York (2018) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
