nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Properties of Plain, Pure, and Safe Petri Nets

verfasst von : Kamila Barylska, Eike Best, Uli Schlachter, Valentin Spreckels

Erschienen in: Transactions on Petri Nets and Other Models of Concurrency XII

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

A set of necessary conditions for a Petri net to be plain, pure and safe is given. Some applications of these conditions both in practice (for Petri net synthesis), and in theory (e.g., as part of a characterisation of the reachability graphs of live and safe marked graphs) are described.

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

Nächstes Kapitel Similarity-Based Approaches for Determining the Number of Trace Clusters in Process Discovery

Unless infinite nets are considered, which we shall exclude in this paper.

Characterisations have been obtained for more restricted classes, e.g. in [4].

S can also be considered as a set of vertices and \(\rightarrow \) as a set of edges of a directed graph, labelled by letters from T.

In this paper, no arc weights greater than 1 will be considered.

This can be verified easily by playing the “token game” in the latter.

Note that p is the only unsafe place (with bound 2), and that \(L'\) is the only non-safe reachable marking. In this sense, the example demonstrates that the conjecture is sharp. We also believe that it is the smallest example with this property.

For P1 and the other properties, see Definitions 1 and 2.

Note that there is also a short path \(s_a[a\rangle 1[c\rangle 2[d\rangle 4[a\rangle 5[c\rangle s_b\) containing a two times. However, this path is not indicative of an unsafe place from a to b, since \(s_a\notin Seq(b)\).

Badouel, É., Bernardinello, L., Darondeau, P.: The synthesis problem for elementary nets is NP-complete. Theor. Comput. Sci. 186, 107–134 (1997)MathSciNetCrossRefMATH

Badouel, E., Bernardinello, L., Darondeau, P.: Petri Net Synthesis. Texts in Theoretical Computer Science. An EATCS Series, p. 339. Springer, Heidelberg (2015). doi:10.1007/978-3-662-47967-4 CrossRefMATH

Best, E., Devillers, R.: Sequential and concurrent behaviour in Petri net theory. Theor. Comput. Sci. 55(1), 87–136 (1987)MathSciNetCrossRefMATH

Best, E., Devillers, R.: Characterisation of the state spaces of marked graph Petri nets. In: Selected papers of LATA 2014, Information and Computation, vol. 253, Part 3, pp. 399–410 (2014). http://dx.doi.org/10.1016/j.ic.2016.06.006

Best, E., Schlachter, U.: Analysis of Petri nets and transition systems. In: Proceedings of 8th Interaction and Concurrency Experience, In: Knight, S., Lanese, I., Lafuente, A.L., Vieira, H.T. (eds.) 189 of Electronic Proceedings in Theoretical Computer Science, pp. 53–67, June 2015. http://eptcs.web.cse.unsw.edu.au/paper.cgi?ICE2015.6, https://github.com/CvO-Theory/apt

Commoner, F., Holt, A.W., Even, S., Pnueli, A.: Marked directed graphs. J. Comput. Syst. Sci. 5(5), 511–523 (1971)MathSciNetCrossRefMATH

Cortadella, J., Kishinevsky, M., Lavagno, L., Yakovlev, A.: Deriving petri nets for finite transition systems. IEEE Trans. Comput. 47(8), 859–882 (1998)MathSciNetCrossRef

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

Landweber, L.H., Robertson, E.L.: Properties of conflict-free and persistent Petri nets. JACM 25(3), 352–364 (1978)MathSciNetCrossRefMATH

10.

Lehmann, D., Pnueli, A., Stavi, J.: Impartiality, justice and fairness: the ethics of concurrent termination. In: Even, S., Kariv, O. (eds.) ICALP 1981. LNCS, vol. 115, pp. 264–277. Springer, Heidelberg (1981). doi:10.1007/3-540-10843-2_22 CrossRef

11.

Ochmański, E.: On conflict-free executions of elementary nets. Systems Science, 27, Nr. 2, Wydawca Oficyna Wydawnicza Politechniki Wrocławskiej, 89–105. Also: Persistent Runs in Elementary Nets. FolCo Technical report, Nicol. Copernic. Univ. of Toruń, 2014 (2001)

12.

Ochmański, E.: Occurrence traces: processes of elementary net systems. In: Rozenberg, G. (ed.) APN 1987. LNCS, vol. 340, pp. 331–342. Springer, Heidelberg (1988). doi:10.1007/3-540-50580-6_36 CrossRef

13.

Pomello, L., Simone, C.: An algebraic characterisation of elementary net system (observable) state space. Formal Aspects Comput. 4(6A), 612–637 (1992)CrossRefMATH

14.

Reisig, W.: Petri Nets: An Introduction. Monographs in Theoretical Computer Science. An EATCS Series, vol. 4. Springer, Heidelberg (1985). doi:10.1007/978-3-642-69968-9 CrossRefMATH

15.

Rozenberg, G.: Behaviour of elementary net systems. In: Brauer, W., Reisig, W., Rozenberg, G. (eds.) ACPN 1986. LNCS, vol. 254, pp. 60–94. Springer, Heidelberg (1987). doi:10.1007/978-3-540-47919-2_4 CrossRef

16.

Thiagarajan, P.S.: Elementary net systems. In: Brauer, W., Reisig, W., Rozenberg, G. (eds.) ACPN 1986. LNCS, vol. 254, pp. 26–59. Springer, Heidelberg (1987). doi:10.1007/978-3-540-47919-2_3 CrossRef

17.

Schlachter, U.: Petri net synthesis for restricted classes of nets. In: Kordon, F., Moldt, D. (eds.) PETRI NETS 2016. LNCS, vol. 9698, pp. 79–97. Springer, Cham (2016). doi:10.1007/978-3-319-39086-4_6 CrossRef

Titel: Properties of Plain, Pure, and Safe Petri Nets
verfasst von: Kamila Barylska
Eike Best
Uli Schlachter
Valentin Spreckels
Verlag: Springer Berlin Heidelberg
Buch: Transactions on Petri Nets and Other Models of Concurrency XII
Print ISBN: 978-3-662-55861-4

Electronic ISBN: 978-3-662-55862-1

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-662-55862-1_1

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"