×

Petri net synthesis for restricted classes of nets. (English) Zbl 1346.68140

Kordon, Fabrice (ed.) et al., Application and theory of Petri nets and concurrency. 37th international conference, PETRI NETS 2016, Toruń, Poland, June 19–24, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-39085-7/pbk; 978-3-319-39086-4/ebook). Lecture Notes in Computer Science 9698, 79-97 (2016).
Summary: This paper first recapitulates an algorithm for Petri net synthesis. Then, this algorithm is extended to special classes of Petri nets. For this purpose, any combination of the properties plain, pure, conflict-free, homogeneous, \(k\)-bounded, generalized T-net, generalized marked graph, place-output-nonbranching and distributed can be specified. Finally, a fast heuristic and an algorithm for minimizing the number of places in the synthesized Petri net is presented and evaluated experimentally.
For the entire collection see [Zbl 1337.68013].

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Badouel, E., Bernardinello, L., Darondeau, P.: Polynomial algorithms for the synthesis of bounded nets. In: Mosses, P.D., Nielsen, M., Schwartzbach, M.I. (eds.) TAPSOFT 1995. LNCS, vol. 915, pp. 364–378. Springer, Heidelberg (1995) · doi:10.1007/3-540-59293-8_207
[2] Badouel, E., Bernardinello, L., Darondeau, P.: Petri Net Synthesis. Springer, Heidelberg (2015). http://dx.doi.org/10.1007/978-3-662-47967-4 · Zbl 1351.68003 · doi:10.1007/978-3-662-47967-4
[3] Badouel, E., Caillaud, B., Darondeau, P.: Distributing finite automata through Petri Net synthesis. Formal Asp. Comput. 13(6), 447–470 (2002). http://dx.doi.org/10.1007/s001650200022 · Zbl 1017.68062 · doi:10.1007/s001650200022
[4] Badouel, E., Darondeau, P.: Theory of regions. In: Reisig, W., Rozenberg, G. (eds.) Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, the Volumes are Based on the Advanced Course on Petri Nets, vol. 1491, pp. 529–586. Springer, Heidelberg (1996). http://dx.doi.org/10.1007/3-540-65306-6_22 · Zbl 0926.68088
[5] Barrett, C., Stump, A., Tinelli, C.: The SMT-LIB Standard: Version 2.0. In: Gupta, A., Kroening, D. (eds.) Proceedings of the 8th International Workshop on Satisfiability Modulo Theories, Edinburgh, UK (2010)
[6] Best, E., Darondeau, P.: Petri Net distributability. In: Clarke, E., Virbitskaite, I., Voronkov, A. (eds.) PSI 2011. LNCS, vol. 7162, pp. 1–18. Springer, Heidelberg (2012) · Zbl 1336.68175 · doi:10.1007/978-3-642-29709-0_1
[7] 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, Heidelberg (2014) · Zbl 1362.68200 · doi:10.1007/978-3-319-04921-2_13
[8] Best, E., Devillers, R.R.: State space axioms for t-systems. Acta Informatica 52(2–3), 133–152 (2015). http://dx.doi.org/10.1007/s00236-015-0219-0 · Zbl 1317.68129 · doi:10.1007/s00236-015-0219-0
[9] Best, E., Devillers, R.R.: Synthesis of bounded choice-free Petri Nets. In: Aceto, L., de Frutos-Escrig, D. (eds.) 26th International Conference on Concurrency Theory, CONCUR 2015, Madrid, Spain, September 1–4, 2015. LIPIcs, vol. 42, pp. 128–141. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015). http://dx.doi.org/10.4230/LIPIcs.CONCUR.2015.128 · Zbl 1374.68319
[10] Best, E., Schlachter, U.: Analysis of Petri Nets and transition systems. In: Knight, S., Lanese, I., Lluch-Lafuente, A., Vieira, H.T. (eds.) Proceedings 8th Interaction and Concurrency Experience, ICE 2015, Grenoble, France, 4–5 June 2015. EPTCS, vol. 189, pp. 53–67 (2015). http://dx.doi.org/10.4204/EPTCS.189.6 · doi:10.4204/EPTCS.189.6
[11] Borde, D., Dierkes, S., Ferrari, R., Gieseking, M., Göbel, V., Grunwald, R., von der Linde, B., Lückehe, D., Schlachter, U., Schierholz, C., Schwammberger, M., Spreckels, V.: APT: analysis of Petri nets and labeled transition systems. https://github.com/CvO-Theory/apt
[12] Cabasino, M.P., Giua, A., Seatzu, C.: Identification of Petri Nets from knowledge of their language. Discrete Event Dyn. Syst. 17(4), 447–474 (2007). http://dx.doi.org/10.1007/s10626-007-0025-0 · Zbl 1125.93332 · doi:10.1007/s10626-007-0025-0
[13] Caillaud, B.: Synet: a synthesizer of distributable bounded Petri-nets from finite automata. https://www.irisa.fr/s4/tools/synet/
[14] Carmona, J.: GENET: GEneralised NET synthesis. http://www.cs.upc.edu/ jcarmona/genet.html
[15] Carmona, J.A., Cortadella, J., Kishinevsky, M.: A region-based algorithm for discovering Petri Nets from event logs. In: Dumas, M., Reichert, M., Shan, M.-C. (eds.) BPM 2008. LNCS, vol. 5240, pp. 358–373. Springer, Heidelberg (2008) · Zbl 05359082 · doi:10.1007/978-3-540-85758-7_26
[16] Carmona, J., Cortadella, J., Kishinevsky, M.: New region-based algorithms for deriving bounded petri nets. IEEE Trans. Comput. 59(3), 371–384 (2010). http://dx.doi.org/10.1109/TC.2009.131 · Zbl 1368.68259 · doi:10.1109/TC.2009.131
[17] Carmona, J., Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: A symbolic algorithm for the synthesis of bounded petri nets. In: van Hee and Valk [27], pp. 92–111. http://dx.doi.org/10.1007/978-3-540-68746-7_10 · Zbl 1143.68478 · doi:10.1007/978-3-540-68746-7_10
[18] Christ, J., Hoenicke, J., Nutz, A.: Proof tree preserving interpolation. In: Piterman, N., Smolka, S.A. (eds.) TACAS 2013 (ETAPS 2013). LNCS, vol. 7795, pp. 124–138. Springer, Heidelberg (2013) · Zbl 1381.68152 · doi:10.1007/978-3-642-36742-7_9
[19] Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Petrify: a tool for manipulating concurrent specifications and synthesis of asynchronous controllers (1996) · Zbl 1013.68273
[20] Cortadella, J., Kishinevsky, M., Lavagno, L., Yakovlev, A.: Synthesizing petri nets from state-based models. In: Rudell, R.L. (ed.) Proceedings of the 1995 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 1995, San Jose, California, USA, November 5–9, 1995, pp. 164–171. IEEE Computer Society/ACM (1995). http://dx.doi.org/10.1109/ICCAD.1995.480008 · doi:10.1109/ICCAD.1995.480008
[21] Cortadella, J., Kishinevsky, M., Lavagno, L., Yakovlev, A.: Deriving petri nets for finite transition systems. IEEE Trans. Computers 47(8), 859–882 (1998). http://dx.doi.org/10.1109/12.707587 · doi:10.1109/12.707587
[22] Cortadella, J., et al.: Petrify: a tool for synthesis of Petri nets and asynchronous circuits. http://www.cs.upc.edu/ jordicf/petrify/
[23] Darondeau, P.: Deriving unbounded Petri Nets from formal languages. In: Sangiorgi, D., de Simone, R. (eds.) CONCUR 1998. LNCS, vol. 1466, pp. 533–548. Springer, Heidelberg (1998) · Zbl 0940.68097 · doi:10.1007/BFb0055646
[24] Dijkstra, E.W.: Hierarchical ordering of sequential processes. Acta Informatica 1, 115–138 (1971). http://dx.doi.org/10.1007/BF00289519 · doi:10.1007/BF00289519
[25] 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/BF00264611 · Zbl 0696.68082 · doi:10.1007/BF00264611
[26] Ehrenfeucht, A., Rozenberg, G.: Partial (set) 2-structures. Part II: state spaces of concurrent systems. Acta Inf 27(4), 343–368 (1990) · Zbl 0696.68083 · doi:10.1007/BF00264612
[27] van Hee, K.M., Valk, R. (eds.): Applications and Theory of Petri Nets, 29th International Conference, PETRI NETS 2008, Xi’an, China, 23–27, June 2008. Lecture Notes in Computer Science, vol. 5062 Springer (2008)
[28] Lorenz, R., Mauser, S., Juhás, G.: How to synthesize nets from languages: a survey. In: Henderson, S.G., Biller, B., Hsieh, M., Shortle, J., Tew, J.D., Barton, R.R. (eds.) Proceedings of the Winter Simulation Conference, WSC 2007, Washington, DC, USA, December 9–12, 2007, pp. 637–647. WSC (2007). http://dx.doi.org/10.1109/WSC.2007.4419657 · doi:10.1109/WSC.2007.4419657
[29] van der Werf, J.M.E.M., van Dongen, B.F., Hurkens, C.A.J., Serebrenik, A.: Process discovery using integer linear programming. In: van Hee and Valk [27], pp. 368–387. http://dx.doi.org/10.1007/978-3-540-68746-7_24 · Zbl 1143.68497 · doi:10.1007/978-3-540-68746-7_24
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.