nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

On the Complexity of Simulating Probabilistic Timed Graph Transformation Systems

verfasst von : Christian Zöllner, Matthias Barkowsky, Maria Maximova, Holger Giese

Erschienen in: Graph Transformation

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

To develop future cyber-physical systems, like networks of autonomous vehicles, the modeling and simulation of huge networks of collaborating systems acting together on large-scale topologies is required. Probabilistic Timed Graph Transformation Systems (PTGTSs) have been introduced as a means of modeling a high-level view of these systems of systems. In our previous work, we proposed a simulation scheme based on local search incremental graph matching that can handle large-scale real-world topologies. However, the prohibitive complexity of the graph matching problem underlying the simulation of any GTS variant makes this setup potentially problematic.

In this paper, we present an improved simulation algorithm and identify restrictions that hold for PTGTS high-level models of cyber-physical systems and real-world topologies, for which we can establish favorable worst-case complexity bounds. We show that the worst-case amortized complexity per simulation step is only logarithmic in the number of active collaborating systems (like vehicles) and constant concerning the size of the topology. The theoretical results are confirmed by experiments.

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 Verifying Graph Programs with Monadic Second-Order Logic

Nächstes Kapitel Automated Checking and Completion of Backward Confluence for Hyperedge Replacement Grammars

Note that the additional restrictions in the following definition, compared to [13], do not restrict the expressiveness of PTGTSs as (a) lower bounds for invariants can be replaced by additional conditions with clock constraints for all PTGT rules and (b) higher priority PTGT rules with constraints for the clocks can be emulated by additional pre-conditions for all lower-priority PTGT rules.

The experiments were run on a server with 256 GB RAM and two Intel Xeon E5-2643 CPUs (4 cores/3.4 GHz). Our single-threaded implementation runs using Java 1.8.

Bapodra, M., Heckel, R.: Abstraction and training of stochastic graph transformation systems. In: Cortellessa, V., Varró, D. (eds.) FASE 2013. LNCS, vol. 7793, pp. 312–326. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-37057-1_23CrossRef

Becker, B., Giese, H.: On safe service-oriented real-time coordination for autonomous vehicles. In: Proceedings of ISORC 2008. IEEE (2008). https://doi.org/10.1109/ISORC.2008.13

Beyhl, T., Blouin, D., Giese, H., Lambers, L.: On the operationalization of graph queries with generalized discrimination networks. In: Echahed, R., Minas, M. (eds.) ICGT 2016. LNCS, vol. 9761, pp. 170–186. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-40530-8_11CrossRefMATH

Ehmes, S., Fritsche, L., Schürr, A.: SimSG: rule-based simulation using stochastic graph transformation. J. Object Technol. 18(3), 1–17 (2019). https://doi.org/10.5381/jot.2019.18.3.a1CrossRef

Ehrig, H., Ehrig, K., Prange, U., Taentzer, G.: Fundamentals of Algebraic Graph Transformation. MTCSAES. Springer, Heidelberg (2006). https://doi.org/10.1007/3-540-31188-2CrossRefMATH

Eclipse modeling framework. https://www.eclipse.org/modeling/emf

Giese, H.: Modeling and verification of cooperative self-adaptive mechatronic systems. In: Kordon, F., Sztipanovits, J. (eds.) Monterey Workshop 2005. LNCS, vol. 4322, pp. 258–280. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71156-8_14CrossRef

Giese, H., Hildebrandt, S., Seibel, A.: Improved flexibility and scalability by interpreting story diagrams. Electron. Commun. Eur. Assoc. Softw. Sci. Technol. 18 (2009). https://doi.org/10.14279/tuj.eceasst.18.268

Habel, A., Heckel, R., Taentzer, G.: Graph grammars with negative application conditions. Fundam. Inf. 26(3/4), 287–313 (1996). https://doi.org/10.3233/FI-1996-263404MathSciNetCrossRefMATH

10.

EMF Henshin. https://www.eclipse.org/modeling/emft/henshin

11.

Hildebrandt, S.: On the performance and conformance of triple graph grammar implementations. Ph.D. thesis, University of Potsdam (2014)

12.

Krause, C., Giese, H.: Probabilistic graph transformation systems. In: Ehrig, H., Engels, G., Kreowski, H.-J., Rozenberg, G. (eds.) ICGT 2012. LNCS, vol. 7562, pp. 311–325. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33654-6_21CrossRefMATH

13.

Maximova, M., Giese, H., Krause, C.: Probabilistic timed graph transformation systems. J. Log. Algebraic Methods Program. 101, 110–131 (2018). https://doi.org/10.1016/j.jlamp.2018.09.003MathSciNetCrossRefMATH

14.

Neumann, S.: Modellierung und Verifikation zeitbehafteter Graphtransformationssysteme mittels GROOVE. Master’s thesis, University of Paderborn (2007)

15.

PTGTS simulator project website. https://mdelab.de/ptgts-simulator

16.

RailCab project. https://www.hni.uni-paderborn.de/cim/projekte/railcab

17.

Ráth, I., Vago, D., Varró, D.: Design-time simulation of domain-specific models by incremental pattern matching. In: IEEE Symposium on Visual Languages and Human-Centric Computing, VL/HCC 2008, Herrsching am Ammersee, Germany, 15–19 September 2008, Proceedings, pp. 219–222. IEEE Computer Society (2008). https://doi.org/10.1109/VLHCC.2008.4639089

18.

Syriani, E., Vangheluwe, H.: A modular timed graph transformation language for simulation-based design. Softw. Syst. Model. 12(2), 387–414 (2013). https://doi.org/10.1007/s10270-011-0205-0CrossRef

19.

Tarjan, R.E.: Amortized computational complexity. SIAM J. Algebraic Discrete Methods 6(2), 306–318 (1985). https://doi.org/10.1137/0606031MathSciNetCrossRefMATH

20.

Torrini, P., Heckel, R., Ráth, I.: Stochastic simulation of graph transformation systems. In: Rosenblum, D.S., Taentzer, G. (eds.) FASE 2010. LNCS, vol. 6013, pp. 154–157. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-12029-9_11CrossRef

21.

Zöllner, C., Barkowsky, M., Maximova, M., Schneider, M., Giese, H.: A simulator for probabilistic timed graph transformation systems with complex large-scale topologies. In: Gadducci, F., Kehrer, T. (eds.) ICGT 2020. LNCS, vol. 12150, pp. 325–334. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-51372-6_20CrossRef

Titel: On the Complexity of Simulating Probabilistic Timed Graph Transformation Systems
verfasst von: Christian Zöllner
Matthias Barkowsky
Maria Maximova
Holger Giese
Verlag: Springer International Publishing
Buch: Graph Transformation
Print ISBN: 978-3-030-78945-9

Electronic ISBN: 978-3-030-78946-6

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-78946-6_14

Premium Partner

Bildnachweise

Rittal/© Rittal, NTT Data/© NTT Data, Wildix/© Wildix, Ceyoniq Technology GmbH/© Ceyoniq Technology GmbH, arvato Systems GmbH/© arvato Systems GmbH, Ninox Software GmbH/© Ninox Software GmbH, Everyday Software S.L./© Everyday Software S.L., Redgate/© Redgate, CELONIS Labs GmbH, DC-Datacenter-Group GmbH/© DC-Datacenter-Group GmbH, all for one/© all for one, G Data CyberDefense/© G Data CyberDefense, FAST LTA/© FAST LTA, Vendosoft/© Vendosoft, Kumavision/© Kumavision, Noriis Network AG/© Noriis Network AG, WSW Software GmbH/© WSW Software GmbH

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"