nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Transformation of Petri Nets into Context-Dependent Fusion Grammars

verfasst von : Hans-Jörg Kreowski, Sabine Kuske, Aaron Lye

Erschienen in: Language and Automata Theory and Applications

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

In this paper, we introduce context-dependent fusion grammars as a new type of hypergraph grammars where the application of fusion rules is restricted by positive and negative context conditions. Our main result is that Petri nets can be transformed into these grammars such that the reachable markings are in one-to-one correspondence to the members of the generated language. As a corollary, we get that the membership problem for context-dependent fusion grammars is at least as hard as the reachability problem of Petri nets.

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 Generalized Predictive Shift-Reduce Parsing for Hyperedge Replacement Graph Grammars

Nächstes Kapitel Generalized Register Context-Free Grammars

Kreowski, H.-J., Kuske, S., Lye, A.: Fusion grammars: a novel approach to the generation of graph languages. In: de Lara, J., Plump, D. (eds.) ICGT 2017. LNCS, vol. 10373, pp. 90–105. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-61470-0_6CrossRefMATH

Adleman, L.M.: Molecular computation of solutions to combinatorial problems. Science 266, 1021–1024 (1994)CrossRef

Czerwinski, W., Lasota, S., Lazic, R., Leroux, J., Mazowiecki, F.: The reachability problem for Petri nets is not elementary. CoRR. arXiv.org, abs/1809.07115 (2018)

Kreowski, H.-J.: A comparison between petri-nets and graph grammars. In: Noltemeier, H. (ed.) WG 1980. LNCS, vol. 100, pp. 306–317. Springer, Heidelberg (1981). https://doi.org/10.1007/3-540-10291-4_22CrossRef

Corradini, A.: Concurrent computing: from Petri nets to graph grammars. Electron. Notes Theoret. Comput. Sci. 2, 56–70 (1995)MathSciNetCrossRef

Ehrig, H., Padberg, J.: Graph grammars and Petri net transformations. In: Desel, J., Reisig, W., Rozenberg, G. (eds.) ACPN 2003. LNCS, vol. 3098, pp. 496–536. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27755-2_14CrossRefMATH

Desel, J., Reisig, W.: Place/transition Petri nets. In: Reisig, W., Rozenberg, G. (eds.) ACPN 1996. LNCS, vol. 1491, pp. 122–173. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-65306-6_15CrossRefMATH

Girault, C., Valk, R.: Petri Nets for Systems Engineering. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-662-05324-9CrossRefMATH

Priese, L., Wimmel, H.: Petri-Netze. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-76971-2CrossRefMATH

10.

Best, E., Wimmel, H.: Structure theory of Petri nets. In: Jensen, K., van der Aalst, W.M.P., Balbo, G., Koutny, M., Wolf, K. (eds.) Transactions on Petri Nets and Other Models of Concurrency VII. LNCS, vol. 7480, pp. 162–224. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38143-0_5CrossRefMATH

11.

Reisig, W.: Understanding Petri Nets - Modeling Techniques, Analysis Methods, Case Studies. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-33278-4CrossRefMATH

12.

Ehrig, H., Habel, A.: Graph grammars with application conditions. In: Rozenberg, G., Salomaa, A. (eds.) The Book of L, pp. 87–100. Springer, Berlin (1986). https://doi.org/10.1007/978-3-642-95486-3_7CrossRef

13.

Habel, A., Heckel, R., Taentzer, G.: Graph grammars with negative application conditions. Fundamenta Inform. 26(3,4), 287–313 (1996)MathSciNetMATH

14.

Dediu, A.-H., Klempien-Hinrichs, R., Kreowski, H.-J., Nagy, B.: Contextual hypergraph grammars – a new approach to the generation of hypergraph languages. In: Ibarra, O.H., Dang, Z. (eds.) DLT 2006. LNCS, vol. 4036, pp. 327–338. Springer, Heidelberg (2006). https://doi.org/10.1007/11779148_30CrossRef

15.

Ehrig, H., Hermann, F., Sartorius, C.: Completeness and correctness of model transformations based on triple graph grammars with negative application conditions. In: Proceedings of the 8th International Workshop on Graph Transformation and Visual Modeling Techniques, vol. 18, pp. 1–18 (2009)

16.

Kreowski, H.-J., Kuske, S., Lye, A.: Splicing/fusion grammars and their relation to hypergraph grammars. In: Lambers, L., Weber, J. (eds.) ICGT 2018. LNCS, vol. 10887, pp. 3–19. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-92991-0_1CrossRefMATH

Titel: Transformation of Petri Nets into Context-Dependent Fusion Grammars
verfasst von: Hans-Jörg Kreowski
Sabine Kuske
Aaron Lye
Verlag: Springer International Publishing
Buch: Language and Automata Theory and Applications
Print ISBN: 978-3-030-13434-1

Electronic ISBN: 978-3-030-13435-8

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-13435-8_18

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"

Premium Partner