Theory of Constraints and Application Conditions: From Graphs to High-Level Structures

• Autorzy: Ehrig H. , Ehrig K. , Habel A. , Pennemann K-H.
• Języki publikacji: EN

Abstrakty

EN

Graph constraints and application conditions are most important for graph grammars and transformation systems in a large variety of application areas. Although different approaches have been presented in the literature already there is no adequate theory up to now which can be applied to different kinds of graphs and high-level structures. In this paper, we introduce a general notion of graph constraints and application conditions and show under what conditions the basic results can be extended from graph transformation to high-level replacement systems. In fact, we use the new framework of adhesive HLR categories recently introduced as combination of HLR systems and adhesive categories. Our main results are the transformation of graph constraints into right application conditions and the transformation from right to left application conditions in this new framework. The transformations are illustrated by a railroad control system with rail net constraints and application conditions.

Słowa kluczowe

EN

graph transformation; constraints; application conditions; graphs; high-level structures; adhesive HLR categories

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

Twórcy

autor

Ehrig H.

autor

Ehrig K.

autor

Habel A.

autor

Pennemann K-H.

• Department of Computing Science, University of Oldenburg, Germany,

Bibliografia

• [1] Bottoni, P., Koch, M., Parisi-Presicce, E, Taentzer, G.: Consistency Checking and Yisualization of OCL Constraints, in: UML 2000, vol. 1939 of Lecture Notes in Computer Science, Springer-Verlag, 2000, 294-308.
• [2] Corradini, A., Montanari, U., Rossi, R, Ehrig, H., Heckel, R., Lowe, M.: Algebraic Approaches lo Graph Transformation. Part I: Basic Concepts and Double Pushout Approach, in: Handbook of Graph Grammars and Computing by Graph Transformation, vol. l, World Scientific, 1997, 163-245.
• [3] Ehrig, H.: Introduction to the Algebraic Theory of Graph Grammars, in: Graph-Grammars and Their Application to Computer Science and Biology, vol. 73 of Lecture Notes in Computer Science, Springer-Verlag, 1979, 1-69.
• [4] Ehrig, H., Ehrig, K., Habe], A., Pennemann, K.-H.: Constraints and Application Conditions: Erom Graphs to High-Level Structures, in: Graph Transformations (1CGT'04), vol. 3256 of Lecture Notes in Computer Science, Springer-Verlag, 2004, 287-303.
• [5] Ehrig, H., Ehrig, K., Prange, U., Taentzer, G.: Fundamental Theory of Typed Attributed Graph Transforma-tion based on Adhesive HLR-Categories, Fundamenta Informaticae, 2005, This volume.
• [6] Ehrig, H., Habel, A.: Graph Grammars with Application Conditions, in: The Book of L (G. Rozenberg, A. Salomaa, Eds.), Springer-Verlag, Berlin, 1986, 87-100.
• [7] Ehrig, H., Habel, A., Kreowski, H.-J., Parisi-Presicce, E: Parallelism and Concurrency in High Level Re-placement Systems, Mathematical Structures in Computer 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, 2005, This volume.
• [9] Ehrig, H., Heckel, R., Korff, M., Loewe, M., Ribeiro, L., Wagner, A., Corradini, A.: Algebraic Approaches to Graph Transformation. Part II: Single-Pushout Approach and Comparison with Double Pushout Approach, in: Handbookof Graph Grammars unii Computing by Graph Transformation, vol. l, World Scientific. 1997. 247-312.
• [10] Ehrig, H.,Lambers, L., Prange, U.: Weak AdhesiveHigh Level Replacement Categories and Systems: A Uniform Framework for Graphs and Petri Net Transformations, Lecture Notes in Computer Science, Springer-Verlag, 2005/2006.
• [l 1] Habel, A., Heckel, R., Taentzer, G.: Graph Grammars with Negative Application Conditions, Fundamenta Informaticae, 26, 1996,287-313.
• [12] Habel, A., Miiller, J., Plump, D.: Double-Pushout Graph Transformation Revisited, Mathematical Structures in Computer Science, 11(5), 2001, 637-688.
• [13] Habel, A., Pennemann, K.-H.: Nested Constraints and Application Conditions for High-Level Structures, in: Formal Methods in Software and System Modeling (H.-J. Kreowski, U. Montanari, F. Orejas, G. Rozenberg, G. Taentzer, Eds.), vol. 3393 of Lecture Notes in Computer Science, Springer-Verlag, 2005, 293-308.
• [14] Habel, A., Pennemann, K.-H.: Nested Constraints and Application Conditions for High-Level Structures (Long Yersion), 2005, In preparation.
• [15] Heckel, R., Wagner, A.: Ensuring Consistency of Conditional Graph Grammars - A Constructive Approach, in: Joint COMPUGRAPH/SEMAGRAPH Workshop on Graph Rewrińng and Computation (SECRA-GRA '95), vol. 2 of Electronic Notes in Theoretical Computer Science, 1995, 95-104.
• [16] Koch, M., Mancini, L. Y, Parisi-Presicce, F.: FoundationsforaGraph-Based Approach to theSpecificationof Access Control Policies, in: Proc. Foundations of Software Science and Computation Structures (FOSSACS 2001), vol. 2030 of Lecture Notes in Computer Science, Springer-Verlag, 2001, 287-302.
• [17] Koch, M., Mancini, L. V., Parisi-Presicce, F.: A Graph-based Formalism for RBAC, ACM Transactions on Information and System Security (TISSEC), 5 (3), 2002, 332-365.
• [18] Koch, M., Mancini, L. Y, Parisi-Presicce, F: Graph-based Specification of Access Control Policies, Journal of Computer and System Sciences, 71, 2005, 1-33.
• [19] Koch, M., Parisi-Presicce, E: Describing Policies with Graph Constraints and Rules, in: Graph Transformation (ICGT2002), vol. 2505 of Lecture Notes in Computer Science, Springer-Verlag, 2002, 223-238.
• [20] Lack, S., Sobociński, P: Adhesive Categories, in: Proc. of Foundations of Software Science and Computation Structures (FOSSACS'04), vol. 2987 of Lecture Notes in Computer Science, Springer-Verlag, 2004, 273-288.
• [21] Mahr, B., Wilharm, A.: Graph Grammars as a Tool for Description in Computer Processed Control: A Case Study, in: Graph-Theoretic Concepts in Computer Science, Hanser Verlag, Müchen, 1982, 165-176.
• [22] Plump, D.: Hypergraph Rewriting: Critical Pairs and Undecidability of Confluence, in: Term Graph Rewriting: Theory- and Practice, John Wiley, New York, 1993, 201-213.
• [23] Rensink, A.: Representing first-order logie by graphs, in: Graph Transformations (ICGT'04), vol. 3256 of Lecture Notes in Computer Science, Springer-Verlag, 2004, 319-335.