Fundamental Theory for Typed Attributed Graphs and Graph Transformation based on Adhesive HLR Categories

• Autorzy: Ehrig H. , Ehrig K. , Prange U. , Taentzer G.
• Języki publikacji: EN

Abstrakty

EN

The concept of typed attributed graphs and graph transformation is most significant for modeling and meta modeling in software engineering and visual languages, but up to now there is no adequate theory for this important branch of graph transformation. In this article we give a new formalization of typed attributed graphs, which allows node and edge attribution. The first main result shows that the corresponding category is isomorphic to the category of algebras over a specific kind of attributed graph structure signature. This allows to prove the second main result showing that the category of typed attributed graphs is an instance of ''adhesive HLR categories''. This new concept combines adhesive categories introduced by Lack and Soboci\'nski with the well-known approach of high-level replacement (HLR) systems using a new simplified version of HLR conditions. As a consequence we obtain a rigorous approach to typed attributed graph transformation providing as fundamental results the Local Church-Rosser, Parallelism, Concurrency, Embedding and Extension Theorem and a Local Confluence Theorem known as Critical Pair Lemma in the literature.

Słowa kluczowe

EN

typed attributed graph transformation; adhesive HLR categories; local confluence of transformations; Critical Pair Lemma

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 74, nr 1
• Strony: 31--61
• Opis fizyczny: bibliogr. 25 poz., wykr.

Twórcy

autor

Ehrig H.

autor

Ehrig K.

autor

Prange U.

autor

Taentzer G.

• Technical University of Berlin, Sekr. FR6-1, Franklinstr. 28/29, 10587 Berlin, Germany

Bibliografia

• [1] Bardohl, R.: A Yisual Etwironment for Visual Languages, Science of Computer Pmgramming (SCP), 44(2), 2002,181-203.
• [2] Berthold, M., Fischer, L, Koch, M.: Attributed Craph Transformation with Partia l Attribution, Technical Report 2000-2, March 2000.
• [3] ClaBen, L, Löwe, M.: Scheme Evolution in Object Oriented Models: A Graph Transformation Approach, in: Proc. Workshop on Formal Melhods at the ISCE'95, Seatlle (U.S.A.), 1995.
• [4] Ehrig, H.: Introduction to the Algebraic Theory of Graph Grammars (A Survey), in: Graph Grammars and their Application to Computer Science and Biology, vol. 73 of LNCS, Springer, 1979, 1-69.
• [5] Ehrig, H., Ehrig, K., Habel, A., Pennemann, K.: Constraints and Application Conditions: Erom Graphs to High-Level S truć turę s, Proceedings ofICGT 2004 (H. Ehrig, G. Engels, F. Parisi-Presicce, G. Rozenberg. Eds.), 3256, Springer, 2004, Long yersion to appear in Fundamenta Informaticae.
• [6] Ehrig, H., Engels, G., Kreowski, H.-L, Rozenberg, G., Eds.: Handbookof Graph Grammars and Computing b\ Graph Transformation, Yolume 2: Applications, Languages and Tools, World Scientific, 1999.
• [7] Ehrig, H., Habel, A., Kreowski, H.-J., Parisi-Presicce, F: Parallelism and Concurrency in High-Level Re-placement Systems, Math. Struct. in Comp. Science, l, 1991, 361-404.
• [8] Ehrig, H., Habel, A., Padberg, J., Prange, U.: Adhesive High-Level Replacement Systems: A New Categori-cal Framework for Graph Transformation, Fundamenta Informaticae this issue.
• [9] Ehrig, H., Habel, A., Padberg, J., Prange, U.: Adhesive High-Level Replacement Categories and Systems, in: Proceedings of 1CGT 2004 (H. Ehrig, G. Engels, F. Parisi-Presicce, G. Rozenberg, Eds.), vol. 3256 of LNCS, Springer, 2004, 144-160.
• [10] Ehrig, H., Kreowski, H.-J., Montanari, U., Rozenberg, G., Eds.: Handbook of Graph Grammars and Computing by Graph Transformation. Vol 3: Concurrency, Parallelism and Distribution, World Scientific, 1999.
• [11] Ehrig, H., Mahr, B.: Fundamentals of Algebraic Specification 1: Eąuations and Initial Semantics, vol. 6 of EATCS Monographs on TCS, Springer, Berlin, 1985.
• [12] Ehrig, H., Orejas, E, Braatz, B., Klein, M., Piirainen, M.: A Generic Component Concept for System Mod-eling, in: Proc. FASĘ 2002: Formal Aspecls of Software Engineering, vol. 2306 of LNCS, Springer, 2002,
• [13] Ehrig, H., Prange, U., Taentzer, G.: Fundamenta! Theory for Typed Attributed Graph Transformation, in: Proceedings O/ICGT2004 (H. Ehrig, G. Engels, F. Parisi-Presicce, G. Rozenberg, Eds.), vol. 3256 of LNCS. Springer, 2004, 161-177.
• [14] Ermel, C., Rudolf, M., Taentzer, G.: The AGG-Approach: Languageand Tool Environment, in: Handbook of Graph Grammars and Computing by Graph Transformation, Volume 2 (H. Ehrig, G. Engels, H. -J. Kreowski, G. Rozenberg, Eds.), World Scientific, 1999, 551-603.
• [15] Fischer, L, Koch, M., Taentzer, G., Volle, Y: Distributed Graph Transformation with Application to Yisual Designof Distributed Systems, in: Handbookof Graph Grammars and Computing by Graph Transformation, Yolume 3 (H. Ehrig, H.-J. Kreowski, U. Montanari, G. Rozenberg, Eds.), World Scientific, 1999, 269-340.
• [16] GroBe-Rhode, M.: Semantic Integration of Heterogeneitos Software Specifications, EATCS Monographs on Theoretical Computer Science, Springer, Berlin, 2004.
• [17] Heckel, R., Küster, J., Taentzer, G.: Confluence of Typed Attributed Graph Transformation, in: Proc. ICGT 2002, vol. 2505 of LNCS, Springer, 2002, 161-176. "
• [18] Lack, S., Sobociński, P: Adhesive Categories, in: Proc. FOSSACS2004, vol. 2987 of LNCS, Springer, 2004, 273-288.
• [19] Llabres, M., Rossello, E: Pushout Complements for Arbitrary Partial Algebras, in: Theory and Applications of Graph Transformation (H. Ehrig, G. Engels, H.-J. Kreowski, G. Rozenberg, Eds.), vol. 1764 of LNCS. Springer, 2000, 131-144.
• [20] Löwe, M., Korff, M., Wagner, A.: An Algebraic Framework for the Transformation of Attributed Graphs, in: Term Graph Rewriting: Theory and Practice, John Wiley and Sons Ltd., 1993, 185-199.
• [21] Plump, D., Steinert, S.: Towards Graph Programs for Graph Algorithms, in: Proceedings of ICGT 2004 (H. Ehrig, G. Engels, F. Parisi-Presicce, G. Rozenberg, Eds.), vol. 3256 of LNCS, Springer, 2004, 128-143.
• [22] Prange, U.: Confluence of'Adhesive HLR Systems with Applications to Typed Attributed Graph Transformation Systems. Diploma Thesis, Technical Report 2004/22, TU Berlin, 2004.
• [23] Schied, G.: Uber Graphgrammatiken, eine Spezifikationsmethode fiir Programmiersprachen und verteilte Regelsysteme, Arbeitsber. des Inst. fiir math. Maschinen und Datenverarbeitung, PhD Thesis, University of Erlangen, 1992.
• [24] Schurr, A.: Programmed Graph Replacement Systems, in: Handbook of Graph Grammars and Computing by Graph Transformations, Yohime 1: Foundations (G. Rozenberg, Ed.), World Scientific, 1997.
• [25] Wagner, A.: A Formal Object Specification Technique Using Rule-Based Transformation of Partial Algebras, Ph.D. Thesis, TU Berlin, 1997.