Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Intelligent SPARQL Endpoints: Optimizing Execution Performance by Automatic Query Relaxation and Queue Scheduling Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Deciding the Deadlock and Livelock in a Petri Net with a Target Marking Based on Its Basic Unfolding

verfasst von : Guanjun Liu, Kun Zhang, Changjun Jiang

Erschienen in: Algorithms and Architectures for Parallel Processing

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Petri nets are widely used to model and analyse concurrent systems. It is an important study to check the deadlock and/or livelock in Petri nets. These checks are generally carried out by the reachability graph technique and thus the state explosion problem is a big obstacle to this technique. The unfolding technique can effectively avoid/alleviate the state explosion problem, especially for those Petri nets that have many concurrent actions. This paper considers the deadlock and livelock problem in a Petri net with a target state. We propose the notion of basic unfolding. Based on basic unfolding, we present a necessary and sufficient condition to decide whether a Petri net is both deadlock-free and livelock-free.

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 Creating Distributed Execution Plans with BobolangNG
Nächstes Kapitel A New Scalable Approach for Distributed Metadata in HPC
Literatur
1.
van der Aalst, W.M.P.: Workflow verification: finding control-flow errors using Petri-Net-Based techniques. In: Aalst, W.M.P., Desel, J., Oberweis, A. (eds.) Business Process Management. LNCS, vol. 1806, pp. 161–183. Springer, Heidelberg (2000). doi:10.​1007/​3-540-45594-9_​11 CrossRef
2.
Bonet, B., Haslum, P., Khomenko, V., Thiebaux, S., Vogler, W.: Recent advances in unfolding technique. Theoret. Comput. Sci. 551, 84–101 (2014)MathSciNetCrossRefMATH
3.
Clarke, E.M., Grumberg, O., Peled, D.: Modeling Chencking, 1st edn. The MIT Press, Cambridge (1999)
4.
Couvreur, J.M., Poitrenaud, D., Weil, R.: Branching processes of general Petri nets. Fundamenta Informaticae 122, 31–58 (2013)MathSciNetMATH
5.
Chu, F., Xie, X.L.: Deadlock analysis of Petri nets using siphons and mathematical programming. IEEE Trans. Robot Automat. 13, 793–840 (1997)CrossRef
6.
Desel, J., Esparza, J.: Free Choice Petri Nets. Cambridge University Press, Cambridge (1995)CrossRefMATH
7.
8.
Esparza, J., Heljanko, K.: Unfoldings: A Partial-Order Approach to Model Checking. Springer-Verlag, Berlin (2008)MATH
9.
Esparza, J., Romer, S., Vogler, W.: An improvement of McMillan’s unfolding algorithm. Form. Methods Syst. Des. 20(3), 285–310 (2002)CrossRefMATH
10.
Khomenko, V.: Model checking based on prefixes of Petri net unfoldings. University of Newcastle upon Tyne (Ph.D. Dissertation) (2003)
11.
12.
Liu, G.J., Liu, C.J., Chao, D.: A necessary and sufficient condition for the liveness of normal nets. Comput. J. 54, 157–163 (2011)CrossRef
13.
Liu, G.J., Jiang, C.J., Zhou, M.C., Ohta, A.: The liveness of WS\(^3\)PR: complexity and decision. IEICE Trans. Fundam. E96–A, 1783–1793 (2013)CrossRef
14.
Liu, G.J., Reisig, W., Jiang, C.J., Zhou, M.C.: A branching-process-based method to check soundness of workflow systems. IEEE Access 4, 4104–4118 (2016)CrossRef
15.
16.
McMillan, K.L.: A technique of state space search based on unfolding. Formal Meth. Syst. Des. 6, 45–65 (1995)CrossRefMATH
17.
Reisig, W.: Understanding Petri Nets: Modeling Techniques, Analysis Methods, Case Studies. Springer, Heidelberg (2013)CrossRefMATH
18.
19.
Dingle, N.J., Knottenbelt, W.J., Suto, T.: PIPE2: a tool for the performance evaluation of generalised stochastic Petri Nets. ACM SIGMETRICS Perform. Eval. Rev. 36(4), 34–39 (2009)CrossRef
Metadaten
Titel
Deciding the Deadlock and Livelock in a Petri Net with a Target Marking Based on Its Basic Unfolding
verfasst von
Guanjun Liu
Kun Zhang
Changjun Jiang
Copyright-Jahr
2016
Buch
Algorithms and Architectures for Parallel Processing

Print ISBN: 978-3-319-49582-8

Electronic ISBN: 978-3-319-49583-5

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-49583-5_7

Premium Partner

    Bildnachweise