Adhesive High-Level Replacement Systems: A New Categorical Framework for Graph Transformation

• Autorzy: Ehrig H. , Padberg J. , Prange U.
• Języki publikacji: EN

Abstrakty

EN

Adhesive high-level replacement (HLR) systems are introduced as a new categorical framework for graph transformation in the double pushout (DPO) approach, which combines the well-known concept of HLR systems with the new concept of adhesive categories introduced by Lack and Sobociński. In this paper we show that most of the HLR properties, which had been introduced to generalize some basic results from the category of graphs to high-level structures, are valid already in adhesive HLR categories. This leads to a smooth categorical theory of HLR systems which can be applied to a large variety of graphs and other visual models. As a main new result in a categorical framework we show the Critical Pair Lemma for the local confluence of transformations. Moreover we present a new version of embeddings and extensions for transformations in our framework of adhesive HLR systems.

Słowa kluczowe

EN

high-level replacement systems; adhesive categories; adhesive HLR categories; graph transformation; local confluence of transformations; Critical Pair Lemma

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

Twórcy

autor

Ehrig H.

autor

Padberg J.

autor

Prange U.

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

Bibliografia

• [1] Baader, F., Nipkow, T.: Term Rewńńng and All That, Cambridge University Press, 1998
• [2] Brown, R., Janelidze, G.: Van Kampen Theorems for Categories of Covering Morphisms in Lextensive Categories, Journal of Pure and Applied Algebra, 119, 1997,255-263.
• [3] Corradini, A., Ehrig, H., Heckel, R., Lówe, M., Montanari, U., Rossi, F.: Algebraic Approaches to Graph Transformat! o n I : Basic Concepts and Double Pushout Approach, in: Handbook of Graph Grammars and Compiiting by Graph Transformańon, Yolume l: Foundations (G. Rozenberg, Ed.), chapter 3, World Scientific, 1997.
• [4] Corradini, A., Gadducci, E: On Term Graphs as an Adhesive Category, Workshop Termgraph 2004, ENTCS, Elsevier, 2004.
• [5] 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.
• [6] Ehrig, H.: Bigraphs meet Double Pushouts, EATCS Bulleńn No. 78, 2002, 72-85.
• [7] Ehrig, H., Ehrig, K., Habel, A., Pennemann, K.: Theory of Constraints and Application Conditions: From Graphs to High-Level Structures, Fundamenta Informańcae, 2005, this issue.
• [8] Ehrig, H., Ehrig, K., Prange, U., Taentzer, G.: Fundamental Theory for Ty pęd Attributed Graphs and Graph Transformation, Fundamenta Informaticae, 2005, this issue.
• [9] Ehrig, H., Gajewsky, M., Parisi-Presicce, E: High-Level Replacement Systems with Applications to Algebraic Specifications and Petri Nets, in: Handbook of Graph Grammars and Compitting by Graph Transfor-mations, Yolume 3: Concurrency, Parallelism, and Distribution (G. Rozenberg, U. Montanari, H. Ehrig, H.-J. Kreowski, Eds.), chapter 6, World Scientific, 1999, 341-400.
• [10] Ehrig, H., Habel, A., Kreowski, H.-J., Parisi-Presicce, E: Parallelism and Concurrency in High-Level Replacement Systems, Math. Struct. in Comp. Science, l, 1991, 361-404.
• [l1] Ehrig, H., Habel, A., Padberg, J., Prange, U.: Adhesive High-Level Replacement Categories and Systems, in: Proceedings of ICGT 2004 (H. Ehrig, G. Engels, F. Parisi-Presicce, G. Rozenberg, Eds.), vol. 3256 of LNCS, Springer, 2004, 144-160.
• [12] Ehrig, H., Konig, B.: Deriving Bisimulation Congruences in the DPO Approach to Graph Rewriting, in: Proc. FOSSACS2004, vol. 2987 of LNCS, Springer, 2004, 151-166.
• [13] Ehrig, H., Orejas, F, Braatz, B., Klein, M., Piirainen, M.: A Generic Component Concept for System Mod-eling, in: Proc. FASE 2002, vol. 2306 of LNCS, Springer, 2002, 33-18.
• [14] Ehrig, H., Orejas, F, Braatz, B., Klein, M., Piirainen, M.: A Component Framework for System Modeling Based on High-Level Replacement Systems, Software and Systems Modeling 3(2), 2004, 114-134.
• [15] Ehrig, H., Prange, U.: Weak Adhesive High-Level Replacement Categories and Systems: A Unifying Framework for Graph and Petri Net Transformat i on s, in: Algebra, Meaning and Computation, LNCS, Springer, 2006, To appear.
• [16] Ehrig, H., Prange, U., Taentzer, G.: Fundamental Theory for Typed Attributed Graph Transformation, in: Proceedings of ICGT 2004 (H. Ehrig, G. Engels, F. Parisi-Presicce, G. Rozenberg, Eds.), vol. 3256 of LNCS, Springer, 2004, 161-177.
• [17] Heckel, R., Kiister, J., Taentzer, G.: Confluence of Typed Attributed Graph Transformation, in: P mc. ICGT 2002, vol. 2505 ofLNCS, Springer, 2002, 161-176.
• [18] Lack, S., Sobociński, R: Adhesive Categories, in: Proc. of FOSSACS '04, vol. 2987 of LNCS, Springer, 2004,273-288.
• [19] Lack, S., Sobociński, P: Adhesive and Quasiadhesive Categories, Theoretical Informatics and Applications, 39(3), 2005, 511-546.
• [20] Lambek, J., Scolt, R: Introduction to Higher Order Categorical Logic, Cambridge University Press, 1986.
• [21] Leifer, J., Milner, R.: Deriving Bisimulation Congruences for Reactive Systems, in: Proc. CONCUR 2000, vol. 1877 of LNCS, Springer, 2000, 243-258.
• [22] Lowe, M., Korff, M., Wagner, A.: Ań Algebraic Framework for the Transformation of Attributed Graphs, in: Term Graph Rewriting: Theory and Practice, John Wiley and Sons Ltd., 1993, 185-199.
• [23] MacLane, S.: Categories for the Working Mathematician, Springer, 1972.
• [24] Padberg, J., Ehrig, H., Ribeiro, L.: Algebraic High-Level Net Transformation Systems, in: Mathematical Structures in Computer Science Vol 2, 1995, 217-256.
• [25] Padberg, J., Taentzer, G.: Embedding of Derivations in High-Level Replacement Systems, Technical Report 1993/9, TU Berlin, 1993.
• [26] Plump, D.: Hypergraph Rewriting: Critical Pairs and Undecidability of Confluence, in: Term Craph Rewriting: Theory and Practice (M. Sleep, M. Plasmeijer, M. van Eekelen, Eds.), chapter 15, John Wiley & Sons Ltd, 1993, 201-213.
• [27] Prange, U.: Confluence of'Adhesive HLR Systems with Applications to Typed Attributed Graph Transformation Systems. Diploma Thesis, Technical Repoil 2004/22, TU Berlin, 2004.
• [28] Sassone, V., Sobociński, P: Deriving Bisimulation Congruences: 2-Categories vs Prec alegorie s, in: Proc. FOSSACS 2003, vol. 2620 ofLNCS, Springer, 2003, 409-424.
• [29] Sobociński, P: Deriving Process Congruences fmm Reaction Rules, Ph.D. Thesis, BRICS Dissertation Series, 2004.