Abstract
In model-driven design, the structure of software is commonly specified by meta-models like uml class diagrams. In this paper we study how graph grammars can be used for this purpose, using statecharts as an example. We extend context-free hyperedge-replacement—which is not powerful enough for this application—so that rules may not only access the nodes attached to the variable on their left-hand side, but also nodes elsewhere in the graph. Although the resulting notion of contextual hyperedge replacement preserves many properties of the context-free case, it has considerably more generative power—enough to specify software models that cannot be specified by class diagrams.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bakewell, A., Plump, D., Runciman, C.: Specifying pointer structures by graph reduction. Mathematical Structures in Computer Science (2011) (accepted for publication)
Drewes, F., Hoffmann, B., Janssens, D., Minas, M.: Adaptive star grammars and their languages. Theoretical Computer Science 411(34-36), 3090–3109 (2010)
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.) AGTIVE 2007. LNCS, vol. 5088, pp. 201–216. Springer, Heidelberg (2008)
Drewes, F., Hoffmann, B., Minas, M.: Context-exploiting shapes for diagram transformation. Machine Graphics and Vision 12(1), 117–132 (2003)
Ehrig, H., Ehrig, K., Prange, U., Taentzer, G.: Fundamentals of Algebraic Graph Transformation. EATCS Monographs on Theoretical Computer Science. Springer (2006)
Engelfriet, J.: Context-Free Graph Grammars. In: Handbook of Formal Languages. Beyond Words, ch. 3, pp. 125–213. Springer (1999)
Habel, A.: Hyperedge Replacement: Grammars and Languages. LNCS, vol. 643. Springer, Heidelberg (1992)
Habel, A., Radke, H.: Expressiveness of graph conditions with variables. In: Ermel, C., Ehrig, H., Orejas, F., Taentzer, G. (eds.) International Colloquium on Graph and Model Transformation 2010. ECEASST, vol. 30 (2010)
Harel, D.: On visual formalisms. Communication of the ACM 31(5), 514–530 (1988)
Hoffmann, B.: Shapely hierarchical graph transformation. In: Proc. of the IEEE Symposia. on Human-Centric Computing Languages and Environments, pp. 30–37. IEEE Computer Press (2001)
Hoffmann, B., Minas, M.: Defining models – Meta models versus graph grammars. In: Küster, J.M., Tuosto, E. (eds.) Graph Transformation and Visual Modeling Techniques 2010. ECEASST, vol. 29 (2010)
Minas, M.: Concepts and realization of a diagram editor generator based on hypergraph transformation. Science of Computer Programming 44(2), 157–180 (2002)
Plump, D.: Hypergraph Rewriting: Critical Pairs and Undecidability of Confluence. In: Sleep, M.R., Plasmeijer, M.J., van Eekelen, M.C. (eds.) Term Graph Rewriting, Theory and Practice, pp. 201–213. Wiley & Sons (1993)
Sagiv, M., Reps, T., Wilhelm, R.: Solving shape-analysis problems in languages with destructive updating. ACM Transactions on Programming Languages and Systems 20(1), 1–50 (1998)
Schürr, A., Winter, A., Zündorf, A.: The Progres Approach: Language and Environment. In: Ehrig, H., Engels, G., Kreowski, H.-J., Rosenberg, G. (eds.) Handbook of Graph Grammars and Computing by Graph Transformation. Applications, Languages, and Tools, vol. 2, ch. 13, pp. 487–550. World Scientific (1999)
Uesu, T.: A system of graph grammars which generates all recursively enumerable sets of labelled graphs. Tsukuba Journal of Mathematics 2, 11–26 (1978)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Drewes, F., Hoffmann, B., Minas, M. (2012). Contextual Hyperedge Replacement. In: Schürr, A., Varró, D., Varró, G. (eds) Applications of Graph Transformations with Industrial Relevance. AGTIVE 2011. Lecture Notes in Computer Science, vol 7233. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34176-2_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-34176-2_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34175-5
Online ISBN: 978-3-642-34176-2
eBook Packages: Computer ScienceComputer Science (R0)