zbMATH — the first resource for mathematics

An institution for graph transformation. (English) Zbl 1312.68112
Mossakowski, Till (ed.) et al., Recent trends in algebraic development techniques. 20th international workshop, WADT 2010, Etelsen, Germany, July 1–4, 2010. Revised selected papers. Berlin: Springer (ISBN 978-3-642-28411-3/pbk). Lecture Notes in Computer Science 7137, 160-174 (2012).
Summary: The development of a denotational framework for graph transformation systems proved elusive so far. Despite the existence of many formalisms for modelling various notions of rewriting, the lack of an explicit, algebraic notion of “term” for describing a graph (thus different from the usual view of a graph as an algebra in itself) frustrated the efforts of the researchers. Resorting to the theory of institutions, the paper introduces a model for the operational semantics of graph transformation systems specified according to the so-called double-pullback approach.
For the entire collection see [Zbl 1236.68008].
68Q42 Grammars and rewriting systems
68Q55 Semantics in the theory of computing
68Q65 Abstract data types; algebraic specification
Full Text: DOI
[1] Baldan, P., Corradini, A., Montanari, U., Ribeiro, L.: Unfolding Semantics of Graph Transformation. Information and Computation 205(5), 733–782 (2007) · Zbl 1115.68093 · doi:10.1016/j.ic.2006.11.004
[2] Baldan, P., Corradini, A., König, B.: A framework for the verification of infinite-state graph transformation systems. Information and Computation 206(7), 869–907 (2008) · Zbl 1153.68034 · doi:10.1016/j.ic.2008.04.002
[3] Corradini, A., Gadducci, F.: A 2-Categorical Presentation of Term Graph Rewriting. In: Moggi, E., Rosolini, G. (eds.) CTCS 1997. LNCS, vol. 1290, pp. 87–105. Springer, Heidelberg (1997) · Zbl 0889.68085 · doi:10.1007/BFb0026983
[4] Corradini, A., Gadducci, F.: An algebraic presentation of term graphs, via gs-monoidal categories. Applied Categorical Structures 7(4), 299–331 (1999) · Zbl 0949.68121 · doi:10.1023/A:1008647417502
[5] Corradini, A., Montanari, U., Rossi, F.: Graph processes. Fundamenta Informaticae 26(3/4), 241–265 (1996)
[6] Corradini, A.: Concurrent Graph and Term Graph Rewriting. In: Montanari, U., Sassone, V. (eds.) CONCUR 1996. LNCS, vol. 1119, pp. 438–464. Springer, Heidelberg (1996) · doi:10.1007/3-540-61604-7_69
[7] Corradini, A., Heindel, T., Hermann, F., König, B.: Sesqui-Pushout Rewriting. In: Corradini, A., Ehrig, H., Montanari, U., Ribeiro, L., Rozenberg, G. (eds.) ICGT 2006. LNCS, vol. 4178, pp. 30–45. Springer, Heidelberg (2006) · Zbl 1156.68423 · doi:10.1007/11841883_4
[8] Ehrig, H., Kreowski, H.J., Montanari, U., Rozenberg, G. (eds.): Handbook of Graph Grammars and Computing by Graph Transformation. Concurrency, Parallelism and Distribution, vol. 3. World Scientific (1999) · Zbl 0951.68049
[9] Ehrig, H.: Introduction to the Algebraic Theory of Graph Grammars (A Survey). In: Claus, V., Ehrig, H., Rozenberg, G. (eds.) Graph Grammars 1978. LNCS, vol. 73, pp. 1–69. Springer, Heidelberg (1979) · Zbl 0407.68072 · doi:10.1007/BFb0025714
[10] Ehrig, H., Heckel, R., Llabrés, M., Orejas, F., Padberg, J., Rozenberg, G.: Double-Pullback Graph Transitions: A Rule-Based Framework with Incomplete Information. In: Ehrig, H., Engels, G., Kreowski, H.-J., Rozenberg, G. (eds.) TAGT 1998. LNCS, vol. 1764, pp. 85–102. Springer, Heidelberg (2000) · Zbl 0958.68123 · doi:10.1007/978-3-540-46464-8_7
[11] Ferrari, G.L., Montanari, U.: Towards the unification of models for concurrency. In: Trees in Algebra and Programming, pp. 162–176 (1990) · Zbl 0758.68027 · doi:10.1007/3-540-52590-4_47
[12] Goguen, J.A., Burstall, R.M.: Institutions: Abstract model theory for specification and programming. Journal of ACM 39(1), 95–146 (1992) · Zbl 0799.68134 · doi:10.1145/147508.147524
[13] Große-Rhode, M., Parisi-Presicce, F., Simeoni, M.: Formal software specification with refinements and modules of typed graph transformation systems. Journal of Computer and System Sciences 64(2), 171–218 (2002) · Zbl 1013.68066 · doi:10.1006/jcss.2001.1800
[14] Heckel, R., Ehrig, H., Wolter, U., Corradini, A.: Double-pullback transitions and coalgebraic loose semantics for graph transformation systems. Applied Categorical Structures 9(1), 83–110 (2001) · Zbl 0970.68116 · doi:10.1023/A:1008734426504
[15] Heckel, R., Llabrés, M., Ehrig, H., Orejas, F.: Concurrency and loose semantics of open graph transformation systems. Mathematical Structures in Computer Science 12(4), 349–376 (2002) · Zbl 1009.68095 · doi:10.1017/S0960129501003553
[16] Kreowski, H.J., Kuske, S.: Approach-Independent Structuring Concepts for Rule-Based Systems. In: Wirsing, M., Pattinson, D., Hennicker, R. (eds.) WADT 2003. LNCS, vol. 2755, pp. 299–311. Springer, Heidelberg (2003) · Zbl 1278.68122 · doi:10.1007/978-3-540-40020-2_17
[17] Kreowski, H.-J., Kuske, S., Rozenberg, G.: Graph Transformation Units - An Overview. In: Degano, P., De Nicola, R., Meseguer, J. (eds.) Montanari Festschrift. LNCS, vol. 5065, pp. 57–75. Springer, Heidelberg (2008) · Zbl 1144.68032 · doi:10.1007/978-3-540-68679-8_5
[18] Kuske, S.: Parameterized transformation units. In: Bauderon, M., Corradini, A. (eds.) GETGRATS Closing Workshop. Electronic Notes in Theoretical Computer Science, vol. 51, pp. 246–257. Elsevier (2001)
[19] Lack, S., Sobociński, P.: Adhesive and quasiadhesive categories. Informatique Théorique et Applications/Theoretical Informatics and Applications 39(3), 511–545 (2005) · Zbl 1078.18010 · doi:10.1051/ita:2005028
[20] Löwe, M.: Algebraic approach to single-pushout graph transformation. Theoretical Computer Science 109(1/2), 181–224 (1993) · Zbl 0787.18001 · doi:10.1016/0304-3975(93)90068-5
[21] Meseguer, J.: Conditional rewriting logic as a unified model of concurrency. Theoretical Computer Science 96(1), 73–155 (1992) · Zbl 0758.68043 · doi:10.1016/0304-3975(92)90182-F
[22] Mossakowski, T., Roggenbach, M.: Structured CSP - A Process Algebra as an Institution. In: Fiadeiro, J.L., Schobbens, P.-Y. (eds.) WADT 2006. LNCS, vol. 4409, pp. 92–110. Springer, Heidelberg (2007) · Zbl 1196.68159 · doi:10.1007/978-3-540-71998-4_6
[23] Orejas, F., Pino, E., Ehrig, H.: Institutions for logic programming. Theoretical Computer Science 173(2), 485–511 (1997) · Zbl 0901.68027 · doi:10.1016/S0304-3975(96)00164-8
[24] Rozenberg, G. (ed.): Handbook of Graph Grammars and Computing by Graph Transformation. Foundations, vol. 1. World Scientific (1997) · Zbl 0908.68095
[25] Sannella, D., Tarlecki, A.: Specifications in an arbitrary institution. Information and Computation 76(2/3), 165–210 (1988) · Zbl 0654.68017 · doi:10.1016/0890-5401(88)90008-9
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.