nach oben

Acta Informatica

Erschienen in:

01.09.2015 | Original Article

Contextual hyperedge replacement

verfasst von: Frank Drewes, Berthold Hoffmann

Erschienen in: Acta Informatica | Ausgabe 6/2015

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Contextual hyperedge-replacement grammars (contextual grammars, for short) are an extension of hyperedge replacement grammars. They have recently been proposed as a grammatical method for capturing the structure of object-oriented programs, thus serving as an alternative to the use of meta-models like uml class diagrams in model-driven software design. In this paper, we study the properties of contextual grammars. Even though these grammars are not context-free, one can show that they inherit several of the nice properties of hyperedge replacement grammars. In particular, they possess useful normal forms and their membership problem is in NP.

Vorheriger Artikel Some properties of involution binary relations

Nächster Artikel Parametrized invariance for infinite state processes

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 "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

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

Recall that \([ sq ]\) denotes the set of symbols that occur in \( sq \).

We can use \(\dot{\fancyscript{C}}\) in \(S\langle \dot{\fancyscript{C}}, sq \rangle \) rather than having to guess a subset of \(\dot{\fancyscript{C}}\), because we want \(\Gamma '\) to generate \(L\) rather than the whole language \({\fancyscript{L}}(\Gamma )\).

Recall that, by the remark after Definition 2.3, the requirement \(\dot{Z}=\emptyset \) is no limitation.

Recall that a wpo is a partial order that is well-founded (there are no infinite descending chains) and has no infinite antichains (every infinite subset contains comparable elements).

As Dirk Janssens has pointed out in private communication, this is not sure for the relation of CHR and non-confluent edNCE grammars, which do derive the language of all graphs, thanks to their ability to delete terminal edges during derivations. Then the node replacement grammar generating complete graphs can be extended by (non-confluent) rules that delete arbitrary sets of edges.

Abadi, M., Cardelli, L.: A Theory of Objects. Monographs in Computer Science. Springer, New York (1996)

Bakewell, A., Plump, D., Runciman, C.: Specifying pointer structures by graph reduction. In: Nagl, M., Pfaltz, J., Böhlen, B. (eds.) Applications of Graph Transformation with Industrial Relevance (AGTIVE’03), No. 3062 in Lecture Notes in Computer Science, pp. 30–44. Springer, Berlin (2004)

Blomer, J., Geiß, R.: GrGen.net: A generative system for graph-rewriting, user manual. www.grgen.net (2006–2011)

Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic—A Language-Theoretic Approach, Encyclopedia of Mathematics and Its Applications, vol. 138. Cambridge University Press, Cambridge (2012)CrossRef

Drewes, F., Habel, A., Kreowski, H.J.: Hyperedge replacement graph grammars. In: Rozenberg, G. (ed.) Handbook of Graph Grammars and Computing by Graph Transformation Vol. I: Foundations, chap. 2, pp. 95–162. World Scientific, Singapore (1997)CrossRef

Drewes, F., Hoffmann, B., Janssens, D., Minas, M.: Adaptive star grammars and their languages. Theor. Comput. Sci. 411, 3090–3109 (2010)MATHMathSciNetCrossRef

Drewes, F., Hoffmann, B., Janssens, D., Minas, M., Van Eetvelde, N.: Adaptive star grammars. In: Corradini, A., Ehrig, H., Montanari, U., Ribeiro, L., Rozenberg, G. (eds.) 3rd International Conference on Graph Transformation (ICGT’06), No. 4178 in Lecture Notes in Computer Science, pp. 77–91. Springer, Berlin (2006)

Drewes, F., Hoffmann, B., Janssens, D., Minas, M., Van Eetvelde, N.: Shaped generic graph transformation. In: Schürr, A., Nagl, M., Zündorf, A. (eds.) Applications of Graph Transformation with Industrial Relevance (AGTIVE’07), No. 5088 in Lecture Notes in Computer Science, pp. 201–216. Springer, Berlin (2008)

Drewes, F., Hoffmann, B., Minas, M.: Context-exploiting shapes for diagram transformation. Mach. Graph. Vis. 12(1), 117–132 (2003)

10.

Drewes, F., Hoffmann, B., Minas, M.: Adaptive star grammars for graph models. In: Ehrig, H., Heckel, R., Rozenberg, G., Taentzer, G. (eds.) 4th International Conference on Graph Transformation (ICGT’08), No. 5214 in Lecture Notes in Computer Science, pp. 201–216. Springer, Berlin (2008)

11.

Drewes, F., Hoffmann, B., Minas, M.: Contextual hyperedge replacement. In: Schürr, A., Varró, D., Varró, G. (eds.) Proceedings of Applications of Graph Transformation with Industrial Relevance 2011 (AGTIVE 2011), No. 7233 in Lecture Notes in Computer Science, pp. 182–197. Springer, Berlin (2012)

12.

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

13.

Engelfriet, J.: Context-free graph grammars. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 3: Beyond Words, chap. 3, pp. 125–213. Springer, Berlin (1999)

14.

Habel, A.: Hyperedge Replacement: Grammars and Languages. No. 643 in Lecture Notes in Computer Science. Springer, Berlin (1992)

15.

Habel, A., Radke, H.: Expressiveness of graph conditions with variables. In: Electronic Communications of the EASST 30 (2010). International Colloquium on Graph and Model Transformation (GraMoT’10)

16.

Harary, F.: Graph Theory. Addison-Wesley, Reading, MA (1969)

17.

Hoffmann, B.: Shapely hierarchical graph transformation. In: Proceedings of IEEE Symposia on Human-Centric Computing Languages and Environments, pp. 30–37. IEEE Computer Press, Silver Spring, MD (2001)

18.

Hoffmann, B.: Conditional adaptive star grammars. Electronic Communications of the EASST 26 (2010)

19.

Hoffmann, B.: More on graph rewriting with contextual refinement. In: A. Habel, M. Mosbah, R. Echahed (eds.) Fifth International Workshop on Graph Computational Models (GCM 2014) (2014). Downloadable at http://gcm2014.imag.fr/proceedingsGCM2014.pdf

20.

Hoffmann, B., Minas, M.: Defining models—meta models versus graph grammars. Elect. Comm. of the EASST 29 (2010). In Proceedings of 6th Workshop on Graph Transformation and Visual Modeling Techniques (GT-VMT’10), Paphos, Cyprus

21.

Lange, K.J., Welzl, E.: String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing. Discrete Appl. Math. 16, 17–30 (1987)MATHMathSciNetCrossRef

22.

Minas, M.: Concepts and realization of a diagram editor generator based on hypergraph transformation. Sci. Comput. Program. 44(2), 157–180 (2002)MATHCrossRef

23.

Parikh, R.J.: On context-free languages. J. ACM 13, 570–581 (1966)MATHMathSciNetCrossRef

24.

Rumbaugh, J., Jacobson, I., Booch, G.: The Unified Modeling Language Reference Manual. Object Technology Series, 2nd edn. Addison Wesley, Reading, MA (2004)

25.

Sagiv, M., Reps, T., Wilhelm, R.: Solving shape-analysis problems in languages with destructive updating. ACM Trans. Program. Lang. Syst. 20(1), 1–50 (1998)CrossRef

26.

Van Eetvelde, N.: A graph transformation approach to refactoring. Doctoral thesis, Universiteit Antwerpen (2007)

Titel: Contextual hyperedge replacement
verfasst von: Frank Drewes
Berthold Hoffmann
Publikationsdatum: 01.09.2015
Verlag: Springer Berlin Heidelberg
Erschienen in: Acta Informatica / Ausgabe 6/2015
Print ISSN: 0001-5903
Elektronische ISSN: 1432-0525
DOI: https://doi.org/10.1007/s00236-015-0223-4

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 "Wirtschaft"

Springer Professional "Technik"