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:
The Alignment of Formal, Structured and Unstructured Process Descriptions Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

On Liveness and Deadlockability in Subclasses of Weighted Petri Nets

verfasst von : Thomas Hujsa, Raymond Devillers

Erschienen in: Application and Theory of Petri Nets and Concurrency

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Structural approaches have greatly simplified the analysis of intractable properties in Petri nets, notably liveness. In this paper, we further develop these structural methods in particular weighted subclasses of Petri nets to analyze liveness and deadlockability, the latter property being a strong form of non-liveness.
For homogeneous join-free nets, from the analysis of specific substructures, we provide the first polynomial-time characterizations of structural liveness and structural deadlockability, expressing respectively the existence of a live marking and the deadlockability of every marking.
For the join-free class, assuming structural boundedness and leaving out the homogeneity constraint, we show that liveness is not monotonic, meaning not always preserved upon any increase of a live marking.
Finally, we use this new material to correct a flaw in the proof of a previous characterization of monotonic liveness and boundedness for homogeneous asymmetric-choice nets, published in 2004 and left unnoticed.

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 Modelling and Evaluation of a Control Room Application
Nächstes Kapitel Restricting Hornets to Support Self-adaptive Systems
Fußnoten
1
Moreover, the well-known necessary conditions of liveness based on siphons containing traps or based on the existence of a repetitive vector [3, 5, 18] do not help.
 
2
In this paper, we study siphons that may contain traps, remarkably in JF nets. Hence, we cannot use the results of [3]. Also, our nets will often be structurally repetitive (weakly sur-consistent), which is another well-known necessary condition of structural liveness (Proposition 10 in [18]) that is not sufficient in the HJF class.
 
3
Each of them has traps and is weakly sur-consistent (i.e. structurally repetitive).
 
Literatur
1.
Barkaoui, K., Couvreur, J.-M., Klai, K.: On the equivalence between liveness and deadlock-freeness in Petri nets. In: Ciardo, G., Darondeau, P. (eds.) ICATPN 2005. LNCS, vol. 3536, pp. 90–107. Springer, Heidelberg (2005). doi:10.​1007/​11494744_​7 CrossRef
2.
Barkaoui, K., Minoux, M.: A polynomial-time graph algorithm to decide liveness of some basic classes of bounded Petri nets. In: Jensen, K. (ed.) ICATPN 1992. LNCS, vol. 616, pp. 62–75. Springer, Heidelberg (1992). doi:10.​1007/​3-540-55676-1_​4 CrossRef
3.
Barkaoui, K., Pradat-Peyre, J.-F.: On liveness and controlled siphons in Petri nets. In: Billington, J., Reisig, W. (eds.) ICATPN 1996. LNCS, vol. 1091, pp. 57–72. Springer, Heidelberg (1996). doi:10.​1007/​3-540-61363-3_​4 CrossRef
4.
5.
Desel, J., Esparza, J.: Free Choice Petri Nets. Cambridge Tracts in Theoretical Computer Science, vol. 40. Cambridge University Press, New York (1995)CrossRefMATH
6.
Esparza, J.: Decidability and complexity of Petri net problems – an introduction. In: Reisig, W., Rozenberg, G. (eds.) ACPN 1996. LNCS, vol. 1491, pp. 374–428. Springer, Heidelberg (1998). doi:10.​1007/​3-540-65306-6_​20 CrossRef
7.
Esparza, J., Nielsen, M.: Decidability issues for Petri nets–a survey. BRICS Rep. Ser. (8) (1994)
8.
Heiner, M., Mahulea, C., Silva, M.: On the importance of the deadlock trap property for monotonic liveness. In: International Workshop on Biological Processes and Petri nets (BioPPN), A satellite event of Petri Nets 2010 (2010)
9.
Hujsa, T., Delosme, J.M., Munier-Kordon, A.: Polynomial sufficient conditions of well-behavedness and home markings in subclasses of weighted Petri nets. Trans. Embed. Comput. Syst. 13, 1–25 (2014)CrossRef
10.
Hujsa, T., Delosme, J.M., Munier-Kordon, A.: On liveness and reversibility of equal-conflict Petri nets. Fundam. Inf. 146(1), 83–119 (2016)MathSciNetCrossRefMATH
11.
Jiao, L., Cheung, T.Y., Lu, W.: On liveness and boundedness of asymmetric choice nets. Theor. Comput. Sci. 311(1–3), 165–197 (2004)MathSciNetCrossRefMATH
12.
Lee, E.A., Messerschmitt, D.G.: Synchronous data flow. Proc. IEEE 75(9), 1235–1245 (1987)CrossRef
13.
Lipton, R.: The reachability problem requires exponential space. Technical report 62, Department of Computer Science, Yale University (1976)
14.
Mayr, E.W., Weihmann, J.: Results on equivalence, boundedness, liveness, and covering problems of BPP-Petri nets. In: Colom, J.-M., Desel, J. (eds.) PETRI NETS 2013. LNCS, vol. 7927, pp. 70–89. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38697-8_​5 CrossRef
15.
Mayr, E.W., Weihmann, J.: Complexity results for problems of communication-free Petri nets and related formalisms. Fundam. Inf. 137(1), 61–86 (2015)MathSciNetMATH
16.
Recalde, L., Teruel, E., Silva, M.: Modeling and analysis of sequential processes that cooperate through buffers. IEEE Trans. Robot. Autom. 14(2), 267–277 (1998)CrossRef
17.
18.
Silva, M., Teruel, E., Colom, J.M.: Linear algebraic and linear programming techniques for the analysis of place/transition net systems. In: Reisig, W., Rozenberg, G. (eds.) ACPN 1996. LNCS, vol. 1491, pp. 309–373. Springer, Heidelberg (1998). doi:10.​1007/​3-540-65306-6_​19 CrossRef
19.
Teruel, E.: Structure Theory of Weighted Place/Transition Net Systems: The Equal Conflict Hiatus. Ph.D. thesis, DIEI. University of Zaragoza, Spain (1994)
20.
Teruel, E., Colom, J.M., Silva, M.: Choice-free Petri nets: a model for deterministic concurrent systems with bulk services and arrivals. IEEE Trans. Syst. Man Cybern. Part A 27(1), 73–83 (1997)CrossRef
21.
22.
Metadaten
Titel
On Liveness and Deadlockability in Subclasses of Weighted Petri Nets
verfasst von
Thomas Hujsa
Raymond Devillers
Copyright-Jahr
2017
Buch
Application and Theory of Petri Nets and Concurrency

Print ISBN: 978-3-319-57860-6

Electronic ISBN: 978-3-319-57861-3

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-57861-3_16

Premium Partner

    Bildnachweise