nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Model Transformation with Triple Graph Grammars and Non-terminal Symbols

verfasst von : William da Silva, Max Bureck, Ina Schieferdecker, Christian Hein

Erschienen in: Formal Techniques for Safety-Critical Systems

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

This work proposes a new graph grammar formalism, that introduces non-terminal symbols to triple graph grammars (TGG) and shows how to apply it to solving the model transformation problem. Our proposed formalism seems to suit code generation from models well, outperforms the standard TGG in the grammar size in one evaluated case and is able to express one transformation that we could not express with TGG. We claim, that such advantages make a formal specification written in our formalism easier to validate and less error-prone, what befits safety-critical systems specially well.

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 Abstraction Refinement with Path Constraints for 3-Valued Bounded Model Checking

Anjorin, A., Leblebici, E., Schürr, A.: 20 years of triple graph grammars: a roadmap for future research. Electron. Commun. EASST 73 (2016). https://doi.org/10.14279/tuj.eceasst.73.1031

Anjorin, A., Saller, K., Lochau, M., Schürr, A.: Modularizing triple graph grammars using rule refinement. In: Gnesi, S., Rensink, A. (eds.) FASE 2014. LNCS, vol. 8411, pp. 340–354. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54804-8_24CrossRef

Bardohl, R., Ehrig, H., de Lara, J., Taentzer, G.: Integrating meta-modelling aspects with graph transformation for efficient visual language definition and model manipulation. In: Wermelinger, M., Margaria-Steffen, T. (eds.) FASE 2004. LNCS, vol. 2984, pp. 214–228. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24721-0_16CrossRef

Brandenburg, F.J., Skodinis, K.: Finite graph automata for linear and boundary graph languages. Theor. Comput. Sci. 332(1–3), 199–232 (2005). https://doi.org/10.1016/j.tcs.2004.09.040MathSciNetCrossRefMATH

Drewes, F., Hoffmann, B., Minas, M.: Predictive top-down parsing for hyperedge replacement grammars. In: Parisi-Presicce, F., Westfechtel, B. (eds.) ICGT 2015. LNCS, vol. 9151, pp. 19–34. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21145-9_2CrossRef

Drewes, F., Hoffmann, B., Minas, M.: Predictive shift-reduce parsing for hyperedge replacement grammars. In: de Lara, J., Plump, D. (eds.) ICGT 2017. LNCS, vol. 10373, pp. 106–122. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-61470-0_7CrossRef

Drewes, F., Kreowski, H.J., Habel, A.: Hyperedge replacement graph grammars. In: Handbook Of Graph Grammars and Computing by Graph Transformation: Volume 1: Foundations, pp. 95–162. World Scientific (1997). https://doi.org/10.1142/9789812384720_0002CrossRef

Ehrig, H., Rozenberg, G., Kreowski, H.J., Montanari, U.: Handbook of Graph Grammars and Computing by Graph Transformation, vol. 3. World Scientific, Singapore (1999). https://doi.org/10.1142/3303CrossRefMATH

Engelfiet, J., Rozenberg, G.: A comparison of boundary graph grammars and context-free hypergraph grammars. Inf. Comput. 84(2), 163–206 (1990). https://doi.org/10.1016/0890-5401(90)90038-JMathSciNetCrossRefMATH

10.

Flasiński, M.: Power properties of NLC graph grammars with a polynomial membership problem. Theor. Comput. Sci. 201(1–2), 189–231 (1998). https://doi.org/10.1016/S0304-3975(97)00212-0MathSciNetCrossRefMATH

11.

Flasiński, M.: On the parsing of deterministic graph languages for syntactic pattern recognition. Pattern Recognit. 26(1), 1–16 (1993). https://doi.org/10.1016/0031-3203(93)90083-9MathSciNetCrossRef

12.

Flasiński, M., Flasińska, Z.: Characteristics of bottom-up parsable edNLC graph languages for syntactic pattern recognition. In: Chmielewski, L.J., Kozera, R., Shin, B.-S., Wojciechowski, K. (eds.) ICCVG 2014. LNCS, vol. 8671, pp. 195–202. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11331-9_24CrossRef

13.

Hermann, F., Ehrig, H., Taentzer, G.: A typed attributed graph grammar with inheritance for the abstract syntax of UML class and sequence diagrams. Electron. Notes Theor. Comput. Sci. 211, 261–269 (2008). https://doi.org/10.1016/j.entcs.2008.04.048CrossRefMATH

14.

Hoffmann, B.: Graph transformation with variables. In: Kreowski, H.-J., Montanari, U., Orejas, F., Rozenberg, G., Taentzer, G. (eds.) Formal Methods in Software and Systems Modeling. LNCS, vol. 3393, pp. 101–115. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31847-7_6CrossRef

15.

Janssens, D., Rozenberg, G.: Graph grammars with neighbourhood-controlled embedding. Theor. Comput. Sci. 21(1), 55–74 (1982). https://doi.org/10.1016/0304-3975(82)90088-3MathSciNetCrossRefMATH

16.

Kim, C.: Efficient recognition algorithms for boundary and linear eNCE graph languages. Acta Inform. 37(9), 619–632 (2001). https://doi.org/10.1007/PL00013320MathSciNetCrossRefMATH

17.

Kim, C.: On the structure of linear apex NLC graph grammars. Theor. Comput. Sci. 438, 28–33 (2012). https://doi.org/10.1016/j.tcs.2012.02.038MathSciNetCrossRefMATH

18.

Klar, F., Lauder, M., Königs, A., Schürr, A.: Extended triple graph grammars with efficient and compatible graph translators. In: Engels, G., Lewerentz, C., Schäfer, W., Schürr, A., Westfechtel, B. (eds.) Graph Transformations and Model-Driven Engineering. LNCS, vol. 5765, pp. 141–174. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17322-6_8CrossRefMATH

19.

Rozenberg, G., Welzl, E.: Boundary NLC graph grammars-basic definitions, normal forms, and complexity. Inf. Control. 69(1–3), 136–167 (1986). https://doi.org/10.1016/S0019-9958(86)80045-6MathSciNetCrossRefMATH

20.

Schürr, A.: Specification of graph translators with triple graph grammars. In: Mayr, E.W., Schmidt, G., Tinhofer, G. (eds.) WG 1994. LNCS, vol. 903, pp. 151–163. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-59071-4_45CrossRef

21.

Skodinis, K., Wanke, E.: Neighborhood-preserving node replacements. In: Ehrig, H., Engels, G., Kreowski, H.-J., Rozenberg, G. (eds.) TAGT 1998. LNCS, vol. 1764, pp. 45–58. Springer, Heidelberg (2000). https://doi.org/10.1007/978-3-540-46464-8_4CrossRef

22.

Wanke, E.: Algorithms for graph problems on BNLC structured graphs. Inf. Comput. 94(1), 93–122 (1991). https://doi.org/10.1016/0890-5401(91)90035-ZMathSciNetCrossRefMATH

Titel: Model Transformation with Triple Graph Grammars and Non-terminal Symbols
verfasst von: William da Silva
Max Bureck
Ina Schieferdecker
Christian Hein
Verlag: Springer International Publishing
Buch: Formal Techniques for Safety-Critical Systems
Print ISBN: 978-3-030-12987-3

Electronic ISBN: 978-3-030-12988-0

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-12988-0_10

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"