Top

Published in:

2018 | OriginalPaper | Chapter

Factorisation of Petri Net Solvable Transition Systems

Authors : Raymond Devillers, Uli Schlachter

Published in: Application and Theory of Petri Nets and Concurrency

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In recent papers, general conditions were developed to characterise when and how a labelled transition system may be factorised into non-trivial factors. These conditions combine a local property (strong diamonds) and a global one (separation), the latter being of course more delicate to check. Since one of the aims of such a factorisation was to speed up the synthesis of Petri nets from such labelled transition systems, the problem arises to analyse if those conditions (and in particular the global one) could be simplified, or even dropped, in the special case of Petri net solvable behaviours, i.e., when Petri net synthesis is possible. This will be the subject of the present paper.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Petri Net Synthesis with Union/Find

next chapter A Geometric Characterisation of Event/State Separation

Those properties could be expressed in terms of categories, but we shall refrain from doing this here.

For example, the well-known KANBAN example, or Petri nets with k tokens, n transitions and n places arranged in a cycle.

Otherwise, only reachability graphs for \(n\le 8\) could be measured before running out of memory on the computer used for measurements.

Analysis and Synthesis of Weighted Marked Graph Petri Nets (2018)

Arnold, A.: Finite Transition Systems - Semantics of Communicating Systems. Prentice Hall International Series in Computer Science. Prentice Hall, Upper Saddle River (1994)MATH

Badouel, E., Bernardinello, L., Darondeau, P.: Petri Net Synthesis. TTCSAES. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47967-4CrossRefMATH

Badouel, E., Bernardinello, L., Darondeau, P.: Polynomial algorithms for the synthesis of bounded nets. In: Mosses, P.D., Nielsen, M., Schwartzbach, M.I. (eds.) CAAP 1995. LNCS, vol. 915, pp. 364–378. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-59293-8_207CrossRef

Badouel, E., Bernardinello, L., Darondeau, P.: The synthesis problem for elementary net systems is NP-complete. Theor. Comput. Sci. 186(1–2), 107–134 (1997)MathSciNetCrossRef

Badouel, E., Darondeau, P.: Theory of regions. In: Reisig, W., Rozenberg, G. (eds.) ACPN 1996. LNCS, vol. 1491, pp. 529–586. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-65306-6_22CrossRef

Best, E., Darondeau, P.: A decomposition theorem for finite persistent transition systems. Acta Inf. 46(3), 237–254 (2009). http://dx.doi.org/10.1007/s00236-009-0095-6MathSciNetCrossRef

Best, E., Devillers, R.: Characterisation of the state spaces of live and bounded marked graph Petri nets. In: Dediu, A.-H., Martín-Vide, C., Sierra-Rodríguez, J.-L., Truthe, B. (eds.) LATA 2014. LNCS, vol. 8370, pp. 161–172. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-04921-2_13CrossRefMATH

Best, E., Devillers, R.: Synthesis of bounded choice-free Petri nets. In: Aceto, L., de Frutos-Escrig, D. (eds.) CONCUR 2015. LIPIcs, vol. 42, pp. 128–141. Schloss Dagstuhl (2015). https://doi.org/10.4230/LIPIcs.CONCUR.2015.128

10.

Best, E., Devillers, R.: Pre-synthesis of Petri nets based on prime cycles and distance paths. Science of Computer Programming (2017)

11.

Best, E., Devillers, R., Koutny, M.: Petri Net Algebra. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2001). https://doi.org/10.1007/978-3-662-04457-5CrossRefMATH

12.

Best, E., Devillers, R., Schlachter, U.: Bounded choice-free Petri net synthesis: algorithmic issues. Acta Informatica (2017). https://doi.org/10.1007/s00236-017-0310-9

13.

Best, E., Schlachter, U.: APT: analysis of Petri nets and transition systems. https://github.com/CvO-Theory/apt

14.

Best, E., Schlachter, U.: Analysis of Petri nets and transition systems. In: Knight, S., Lanese, I., Lluch-Lafuente, A., Vieira, H.T. (eds.) ICE 2015. EPTCS, vol. 189, pp. 53–67 (2015). https://doi.org/10.4204/EPTCS.189.6

15.

Cortadella, J., Kishinevsky, M., Lavagno, L., Yakovlev, A.: Deriving Petri nets for finite transition systems. IEEE Trans. Comput. 47(8), 859–882 (1998). http://dx.doi.org/10.1109/12.707587MathSciNetCrossRef

16.

Devillers, R.: Products of transition systems and additions of Petri nets. In: Desel, J., Yakovlev, A. (eds.) ACSD 2016, pp. 65–73. IEEE Computer Society (2016). https://doi.org/10.1109/ACSD.2016.10

17.

Devillers, R.: Factorisation of transition systems. Acta Informatica (2017). https://doi.org/10.1007/s00236-017-0300-y

18.

Dijkstra, E.W.: Hierarchical ordering of sequential processes. Acta Informatica 1, 115–138 (1971). https://doi.org/10.1007/BF00289519MathSciNetCrossRef

19.

Ehrenfeucht, A., Rozenberg, G.: Partial (set) 2-structures. Part I: basic notions and the representation problem. Acta Informatica 27(4), 315–342 (1990). http://dx.doi.org/10.1007/BF00264611MathSciNetCrossRef

20.

Ehrenfeucht, A., Rozenberg, G.: Partial (set) 2-structures. Part II: state spaces of concurrent systems. Acta Informatica 27(4), 343–368 (1990). http://dx.doi.org/10.1007/BF00264612MathSciNetCrossRef

21.

Keller, R.M.: A fundamental theorem of asynchronous parallel computation. In: Feng, T. (ed.) Parallel Processing. LNCS, vol. 24, pp. 102–112. Springer, Heidelberg (1975). https://doi.org/10.1007/3-540-07135-0_113CrossRef

Title: Factorisation of Petri Net Solvable Transition Systems
Authors: Raymond Devillers
Uli Schlachter
Publisher: Springer International Publishing
Book: Application and Theory of Petri Nets and Concurrency
Print ISBN: 978-3-319-91267-7

Electronic ISBN: 978-3-319-91268-4

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-91268-4_5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner