nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

On the Definition of Parallel Independence in the Algebraic Approaches to Graph Transformation

verfasst von : Andrea Corradini

Erschienen in: Software Technologies: Applications and Foundations

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Parallel independence between transformation steps is a basic and well-understood notion of the algebraic approaches to graph transformation, and typically guarantees that the two steps can be applied in any order obtaining the same resulting graph, up to isomorphism. The concept has been redefined for several algebraic approaches as variations of a classical “algebraic” condition, requiring that each matching morphism factorizes through the context graphs of the other transformation step. However, looking at some classical papers on the double-pushout approach, one finds that the original definition of parallel independence was formulated in set-theoretical terms, requiring that the intersection of the images of the two left-hand sides in the host graph is contained in the intersection of the two interface graphs. The relationship between this definition and the standard algebraic one is discussed in this position paper, both in the case of left-linear and non-left-linear rules.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Probabilistic Modelling of Station Locations in Bicycle-Sharing Systems

Nächstes Kapitel Approximating Parikh Images for Generating Deterministic Graph Parsers

The definitions of parallel independence based on Conditions 1 or 2 date back to the mid seventies of last century. Besides of [8] they also appear in [12]. In [17] parallel independence is defined set-theoretically (see diagram (3)) as \(m_1(L_1) \subseteq g_2(D_2) \wedge m_2(L_2) \subseteq g_1(D_1)\), a variant of Condition 2.

The conditions for parallel independence for non-linear rules in the context of RSqPO, presented in [7], are even stronger. First, besides Condition 2, making reference to diagram (4) it is required that \((\rho _2, h_1 \circ m_{2d})\) and \((\rho _1, h_2 \circ m_{1d})\) are (RSqPO-) redexes. Furthermore, and more interestingly for the present discussion, since productions can also be non-right-linear, besides Condition 4 it is also required that the squares in (9) are pullbacks.

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-50230-4_8/436844_1_En_8_Equ9_HTML.gif

(9)

Cockett, J., Lack, S.: Restriction categories II: partial map classification. Theor. Comput. Sci. 294(1–2), 61–102 (2003)MathSciNetCrossRefMATH

Corradini, A., Duval, D., Echahed, R., Prost, F., Ribeiro, L.: AGREE – algebraic graph rewriting with controlled embedding. In: Parisi-Presicce, F., Westfechtel, B. (eds.) ICGT 2015. LNCS, vol. 9151, pp. 35–51. Springer, Heidelberg (2015). doi:10.1007/978-3-319-21145-9_3 CrossRef

Corradini, A., Duval, D., Prost, F., Ribeiro, L.: Parallelism in AGREE transformations. In: Echahed, R., Minas, M. (eds.) ICGT 2016. LNCS, vol. 9761, pp. 37–53. Springer, Heidelberg (2016). doi:10.1007/978-3-319-40530-8_3 CrossRef

Corradini, A., Ehrig, H., Löwe, M., Montanari, U., Rossi, F.: Abstract graph derivations in the double pushout approach. In: Schneider, H.J., Ehrig, H. (eds.) Graph Transformations in Computer Science. LNCS, vol. 776, pp. 86–103. Springer, Heidelberg (1994). doi:10.1007/3-540-57787-4_6 CrossRef

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). doi:10.1007/11841883_4 CrossRef

Corradini, A., Montanari, U., Rossi, F., Ehrig, H., Heckel, R., Löwe, M.: Algebraic approaches to graph transformation - part I: basic concepts and double pushout approach. In: Handbook of Graph Grammars and Computing by Graph Transformations, Foundations, vol. 1, pp. 163–246 (1997)

Danos, V., Heindel, T., Honorato-Zimmer, R., Stucki, S.: Reversible Sesqui-Pushout rewriting. In: Giese, H., König, B. (eds.) ICGT 2014. LNCS, vol. 8571, pp. 161–176. Springer, Heidelberg (2014). doi:10.1007/978-3-319-09108-2_11

Ehrig, H., Rosen, B.: Commutativity of Independent Transformations on Complex Objects. IBM Thomas J. Watson Research Division (1976)

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). doi:10.1007/BFb0025714 CrossRef

10.

Ehrig, H., Ehrig, K., Prange, U., Taentzer, G.: Fundamentals of Algebraic Graph Transformation. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2006)MATH

11.

Ehrig, H., Habel, A., Kreowski, H., Parisi-Presicce, F.: Parallelism and concurrency in high-level replacement systems. Math. Struct. Comput. Sci. 1(3), 361–404 (1991)MathSciNetCrossRefMATH

12.

Ehrig, H., Kreowski, H.-J.: Parallelism of manipulations in multidimensional information structures. In: Mazurkiewicz, A. (ed.) MFCS 1976. LNCS, vol. 45, pp. 284–293. Springer, Heidelberg (1976). doi:10.1007/3-540-07854-1_188 CrossRef

13.

Ehrig, H., Pfender, M., Schneider, H.J.: Graph-grammars: an algebraic approach. In: 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, 15–17 October 1973, pp. 167–180. IEEE Computer Society (1973)

14.

Kreowski, H.: Manipulation von Graphmanipulationen. Ph.D. thesis, Technische Universität, Berlin (1977)

15.

Lack, S., Sobocinski, P.: Adhesive and quasiadhesive categories. Theor. Inf. Appl. 39(3), 511–545 (2005)MathSciNetCrossRefMATH

16.

Löwe, M.: Graph rewriting in span-categories. In: Ehrig, H., Rensink, A., Rozenberg, G., Schürr, A. (eds.) ICGT 2010. LNCS, vol. 6372, pp. 218–233. Springer, Heidelberg (2010). doi:10.1007/978-3-642-15928-2_15 CrossRef

17.

Rosen, B.K.: A Church-Rosser theorem for graph grammars. ACM SIGACT News 7(3), 26–31 (1975)CrossRef

Titel: On the Definition of Parallel Independence in the Algebraic Approaches to Graph Transformation
verfasst von: Andrea Corradini
Verlag: Springer International Publishing
Buch: Software Technologies: Applications and Foundations
Print ISBN: 978-3-319-50229-8

Electronic ISBN: 978-3-319-50230-4

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-50230-4_8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"