Matrix Graph Grammars with Application Conditions

• Autorzy: Velasco P.P.P.
• Języki publikacji: EN

Abstrakty

EN

In the Matrix approach to graph transformation we represent simple digraphs and rules with Boolean matrices and vectors, and the rewriting is expressed using Boolean operators only. In previous works, we developed analysis techniques enabling the study of the applicability of rule sequences, their independence, state reachability and the minimal graph able to fire a sequence. In the present paper we improve our framework in two ways. First, we make explicit (in the form of a Boolean matrix) some negative implicit information in rules. This matrix (called nihilation matrix) contains the elements that, if present, forbid the application of the rule (i.e. potential dangling edges, or newly added edges, which cannot be already present in the simple digraph). Second, we introduce a novel notion of application condition, which combines graph diagrams together with monadic second order logic. This allows for more flexibility and expressivity than previous approaches, as well as more concise conditions in certain cases. We demonstrate that these application conditions can be embedded into rules (i.e. in the left hand side and the nihilation matrix), and show that the applicability of a rule with arbitrary application conditions is equivalent to the applicability of a sequence of plain rules without application conditions. Therefore, the analysis of the former is equivalent to the analysis of the latter, showing that in our framework no additional results are needed for the study of application conditions. Moreover, all analysis techniques of [21, 22] for the study of sequences can be applied to application conditions.

Słowa kluczowe

EN

graph transformation; matrix graph grammars; application conditions; monadic 2nd-order logic; graph dynamics

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 99, nr 1
• Strony: 29--62
• Opis fizyczny: Bibliogr. 34 poz., wykr.

Twórcy

autor

Velasco P.P.P.

• School of Computer Science Universidad Autónoma de Madrid Ciudad Universitaria de Cantoblanco, 28049 - Madrid, Spain,

Bibliografia

• [1] AGG, The Attributed Graph Grammar system. http://tfs.cs.tu-berlin.de/agg/.
• [2] Braket notation intro: http://en.wikipedia.org/wiki/Bra-ket notation
• [3] Corradini, A., Montanari, U., Rossi, F., Ehrig, H., Heckel, R., L¨owe, M. 1999. Algebraic Approaches to Graph Transformation - Part I: Basic Concepts and Double Pushout Approach. In [32], pp.: 163-246
• [4] Courcelle, B. 1997. The expression of graph properties and graph transformations in monadic second-order logic. In [32], pp.: 313-400.
• [5] Ebbinghaus, H.-D.; Flum, J¨org; T. 1994, Mathematical Logic. Springer.
• [6] Ehrig, H., Heckel, R., Korff, M., L¨owe, M., Ribeiro, L., Wagner, A., Corradini, A. 1999. Algebraic Approaches to Graph Transformation - Part II: Single Pushout Approach and Comparison with Double Pushout Approach. In [32], pp.: 247-312.
• [7] Ehrig, H., Ehrig, K., Habel, A., Pennemann, K.-H. Constraints and Application Conditions: From Graphs to High-Level Structures. Proc. ICGT'04. LNCS 3256, pp.: 287-303. Springer.
• [8] Ehrig, H., Ehrig, K., Prange, U., Taentzer, G. 2006. Fundamentals of Algebraic Graph Transformation. Springer.
• [9] Engelfriet, J., Rozenberg, G. 1997. Node Replacement Graph Grammars. In [32], pp.: 1-94.
• [10] Fujaba tool suite home page: http://wwwcs.uni-paderborn.de/cs/fujaba/
• [11] Habel, A., Pennemann, K.-H. Satisfiability of High-Level Conditions. Proc ICGT'06, LNCS 4178, pp.: 430-444. Springer.
• [12] Habel, A., Pennemann, K.-H. 2005. Nested Constraints and Application Conditions for High-Level Structures. In Formal Methods in Software and Systems Modeling, LNCS 3393, pp. 293-308. Springer.
• [13] Habel, A., Penneman, K.-H. 2009. Correctness of High-Level Transformation Systems Relative to Nested Conditions. Math. Struct. Comp. Science 19(2), pp.: 245-296.
• [14] Heckel, R., Küster, J.-M-., Taentzer, G. 2002. Confluence of typed attributed graph transformation systems. Proc. ICGT'02, LNCS 2505, pp. 161-176. Springer.
• [15] Heckel, R.,Wagner, A. 1995. Ensuring consistency of conditional graph rewriting - a constructive approach., Electr. Notes Theor. Comput. Sci. (2).
• [16] Kahl, W. 2002. A Relational Algebraic Approach to Graph Structure Transformation. Tech. Rep. 2002-03, Universitat der BundeswehrMunchen.
• [17] Lambers, L., Ehrig, H., Orejas, F. 2006. Conflict Detection for Graph Transformation with Negative Application Conditions. Proc ICGT'06, LNCS 4178, pp.: 61-76. Springer.
• [18] de Lara, J., Vangheluwe, H. 2002. AT oM3: A tool for multi-formalism modelling and meta-modelling. Proc. FASE'02, LNCS 2306, pp. 174-188. Springer.
• [19] de Lara, J., Vangheluwe, H. 2004. Defining Visual Notations and Their Manipulation Through Meta-Modelling and Graph Transformation. Journal of Visual Languages and Computing. Special section on "Domain-Specific Modeling with Visual Languages", Vol 15(3-4), pp.: 309-330. Elsevier Science.
• [20] Mizoguchi, Y., Kuwahara, Y. 1995. Relational Graph Rewritings. TCS 141:311-328, Elsevier.
• [21] Pérez Velasco, P. P., de Lara, J. 2006. Towards a New Algebraic Approach to Graph Transformation: Long Version. Tech. Rep. of the School of Comp. Sci., Univ. Aut´onoma Madrid. http://www.ii.uam.es/ jlara/investigacion/techrep 03 06.pdf.
• [22] Pérez Velasco, P. P., de Lara, J. 2006. Matrix Approach to Graph Transformation: Matching and Sequences. Proc ICGT'06, LNCS 4178, pp.:122-137. Springer.
• [23] Pérez Velasco, P. P., de Lara, J. 2006. Using Matrix Graph Grammars for the Analysis of Behavioural Specifications: Sequential and Parallel Independence Proc. PROLE'07, pp.: 11-26. Electr. Notes Theor. Comput. Sci. (206). pp.:133-152. Elsevier.
• [24] Pérez Velasco, P. P., de Lara, J. 2007. Analysing Rules with Application Conditions using Matrix Graph Grammars. Graph Transformation for Verification and Concurrency (GTVC) workshop.
• [25] Pérez Velasco, P. P. 2008. Matrix Graph Grammars. E-book available at: http://www.mat2gra.info/, and arXiv:0801.1245v1.
• [26] Pérez Velasco, P. P., de Lara, J. 2009. A Reformulation of Matrix Graph Grammars with Boolean Complexes. The Electronic Journal of Combinatorics. Vol 16(1). R73. Available at: http://www.combinatorics.org/.
• [27] Pérez Velasco, P. P. 2009.Matrix Graph Grammars as aModel of Computation. Preliminary version available at arXiv:arXiv:0905.1202v2.
• [28] Raoult, J.-C., Vosisin, F. 1992. Set-Theoretic Graph Rewriting. INRIA Rapport de Recherche no. 1665.
• [29] Rensink, A. 2004. Representing First-Order Logic Using Graphs. Proc. ICGT'04, LNCS 3256, pp.: 319-335. Springer.
• [30] Rensink, A. 2004. Canonical Graph Shapes. Proc. ESOP'04, LNCS 2986, pp.: 401-415. Springer.
• [31] Rensink, A. 2006. Nested Quantification in Graph Transformation Rules. Proc. ICGT'06, LNCS 4178, pp.: 1-13. Springer.
• [32] Rozenberg, G. 1997. Handbook of Graph Grammars and Computing by Graph Transformation. Vol 1. World Scientific.
• [33] Taentzer, 1996. Parallel and Distributed Graph Transformation. Formal Description and Application to Communication-Based Systems. PhD. Thesis. Shaker Verlag.
• [34] Valiente, G. 1998. Grammatica: An Implementation of Algebraic Graph Transformation on Mathematica. Proc. 6th Works. on Theory and Application of Graph Transformations. pp. 261-267.