Abstract
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.
Research partially supported by the MIUR project SisteR (PRIN 20088HXMYN) and by the FAPERGS/CNPq project 10/0043-0.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baldan, P., Corradini, A., Montanari, U., Ribeiro, L.: Unfolding Semantics of Graph Transformation. Information and Computation 205(5), 733–782 (2007)
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)
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)
Corradini, A., Gadducci, F.: An algebraic presentation of term graphs, via gs-monoidal categories. Applied Categorical Structures 7(4), 299–331 (1999)
Corradini, A., Montanari, U., Rossi, F.: Graph processes. Fundamenta Informaticae 26(3/4), 241–265 (1996)
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)
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)
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)
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)
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)
Ferrari, G.L., Montanari, U.: Towards the unification of models for concurrency. In: Trees in Algebra and Programming, pp. 162–176 (1990)
Goguen, J.A., Burstall, R.M.: Institutions: Abstract model theory for specification and programming. Journal of ACM 39(1), 95–146 (1992)
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)
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)
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)
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)
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)
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)
Lack, S., Sobociński, P.: Adhesive and quasiadhesive categories. Informatique Théorique et Applications/Theoretical Informatics and Applications 39(3), 511–545 (2005)
Löwe, M.: Algebraic approach to single-pushout graph transformation. Theoretical Computer Science 109(1/2), 181–224 (1993)
Meseguer, J.: Conditional rewriting logic as a unified model of concurrency. Theoretical Computer Science 96(1), 73–155 (1992)
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)
Orejas, F., Pino, E., Ehrig, H.: Institutions for logic programming. Theoretical Computer Science 173(2), 485–511 (1997)
Rozenberg, G. (ed.): Handbook of Graph Grammars and Computing by Graph Transformation. Foundations, vol. 1. World Scientific (1997)
Sannella, D., Tarlecki, A.: Specifications in an arbitrary institution. Information and Computation 76(2/3), 165–210 (1988)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 IFIP International Federation for Information Processing
About this paper
Cite this paper
Corradini, A., Gadducci, F., Ribeiro, L. (2012). An Institution for Graph Transformation. In: Mossakowski, T., Kreowski, HJ. (eds) Recent Trends in Algebraic Development Techniques. WADT 2010. Lecture Notes in Computer Science, vol 7137. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-28412-0_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-28412-0_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-28411-3
Online ISBN: 978-3-642-28412-0
eBook Packages: Computer ScienceComputer Science (R0)