{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T22:35:44Z","timestamp":1784241344432,"version":"3.55.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2017,11,20]],"date-time":"2017-11-20T00:00:00Z","timestamp":1511136000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["Be 1267\/15-1"],"award-info":[{"award-number":["Be 1267\/15-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00236-017-0310-9","type":"journal-article","created":{"date-parts":[[2017,11,20]],"date-time":"2017-11-20T05:05:23Z","timestamp":1511154323000},"page":"575-611","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Bounded choice-free Petri net synthesis: algorithmic issues"],"prefix":"10.1007","volume":"55","author":[{"given":"Eike","family":"Best","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raymond","family":"Devillers","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5063-025X","authenticated-orcid":false,"given":"Uli","family":"Schlachter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,11,20]]},"reference":[{"key":"310_CR1","first-page":"339","volume-title":"Petri Net Synthesis. Texts in Theoretical Computer Science","author":"\u00c9 Badouel","year":"2015","unstructured":"Badouel, \u00c9., Bernardinello, L., Darondeau, P.: Petri Net Synthesis. Texts in Theoretical Computer Science, p. 339. Springer, Berlin (2015). ISBN 978-3-662-47967-4"},{"key":"310_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1007\/3-540-59293-8_207","volume-title":"TAPSOFT 1995, Aarhus (Denmark)","author":"\u00c9 Badouel","year":"1995","unstructured":"Badouel, \u00c9., Bernardinello, L., Darondeau, P.: Polynomial algorithms for the synthesis of bounded nets. In: Mosses, P., Nielsen, M., Schwartzbach, M. (eds.) TAPSOFT 1995, Aarhus (Denmark). Lecture Notes in Computer Science, vol. 915, pp. 364\u2013378. Springer, Berlin (1995)"},{"issue":"1\u20132","key":"310_CR3","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0304-3975(96)00219-8","volume":"186","author":"\u00c9 Badouel","year":"1997","unstructured":"Badouel, \u00c9., Bernardinello, L., Darondeau, P.: The synthesis problem for elementary net systems is NP-complete. Theor. Comput. Sci. 186(1\u20132), 107\u2013134 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"310_CR4","first-page":"529","volume-title":"Lectures on Petri Nets I: Basic Models. Lecture Notes in Computer Science","author":"\u00c9 Badouel","year":"1999","unstructured":"Badouel, \u00c9., Darondeau, P.: Theory of regions. In: Reisig, W., Rozenberg, G. (eds.) Lectures on Petri Nets I: Basic Models. Lecture Notes in Computer Science, vol. 1491, pp. 529\u2013586. Springer, Berlin (1999)"},{"key":"310_CR5","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1007\/s001650200022","volume":"13","author":"\u00c9 Badouel","year":"2002","unstructured":"Badouel, \u00c9., Caillaud, B., Darondeau, P.: Distributing finite automata through Petri net synthesis. J. Form. Asp. Comput. 13, 447\u2013470 (2002)","journal-title":"J. Form. Asp. Comput."},{"key":"310_CR6","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/s00236-009-0095-6","volume":"46","author":"E Best","year":"2009","unstructured":"Best, E., Darondeau, P.: A decomposition theorem for finite persistent transition systems. Acta Inf. 46, 237\u2013254 (2009)","journal-title":"Acta Inf."},{"key":"310_CR7","first-page":"1","volume-title":"PSI\u201911, Novosibirsk, LNCS","author":"E Best","year":"2011","unstructured":"Best, E., Darondeau, P.: Petri net distributability. In: Virbitskaite, I., Voronkov, A. (eds.) PSI\u201911, Novosibirsk, LNCS, vol. 7162, pp. 1\u201318. Springer, Berlin (2011)"},{"key":"310_CR8","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/978-3-319-39086-4_4","volume-title":"Proc. 37th International Conference on Applications and Theory of Petri Nets and Concurrency, Toru\u0144 (Poland), Lecture Notes in Computer Science","author":"E Best","year":"2016","unstructured":"Best, E., Erofeev, E., Schlachter, U., Wimmel, H.: Characterising Petri net solvable binary words. In: Moldt, D., Kordon, F. (eds.) Proc. 37th International Conference on Applications and Theory of Petri Nets and Concurrency, Toru\u0144 (Poland), Lecture Notes in Computer Science, vol. 9698, pp. 39\u201358. Springer, Berlin (2016)"},{"key":"310_CR9","doi-asserted-by":"crossref","unstructured":"Best, E., Devillers, R.: Synthesis of persistent systems. In: 35th International Conference on Application and Theory of Petri Nets and Concurrency (ICATPN 2014), pp. 111\u2013129 (2014)","DOI":"10.1007\/978-3-319-07734-5_7"},{"issue":"1","key":"310_CR10","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s00236-014-0209-7","volume":"52","author":"E Best","year":"2015","unstructured":"Best, E., Devillers, R.: Synthesis and reengineering of persistent systems. Acta Inf. 52(1), 35\u201360 (2015)","journal-title":"Acta Inf."},{"issue":"2\u20133","key":"310_CR11","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/s00236-015-0219-0","volume":"52","author":"E Best","year":"2015","unstructured":"Best, E., Devillers, R.: State space axioms for T-systems. Acta Inf. 52(2\u20133), 133\u2013152 (2015)","journal-title":"Acta Inf."},{"key":"310_CR12","first-page":"39","volume":"140","author":"E Best","year":"2015","unstructured":"Best, E., Devillers, R.: Synthesis of live and bounded persistent systems. Fund. Inf. 140, 39\u201359 (2015)","journal-title":"Fund. Inf."},{"key":"310_CR13","doi-asserted-by":"publisher","unstructured":"Best, E., Devillers, R.: Synthesis of bounded choice-free Petri nets. In: Aceto, L., Frutos Escrig, D. (eds.) Proc. 26th International Conference on Concurrency Theory (CONCUR 2015), LIPICS, pp. 128\u2013141. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl. https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2015.128 (2015)","DOI":"10.4230\/LIPIcs.CONCUR.2015.128"},{"issue":"Pt. 3","key":"310_CR14","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1016\/j.ic.2016.06.006","volume":"253","author":"E Best","year":"2017","unstructured":"Best, E., Devillers, R.: Characterisation of the state spaces of marked graph Petri nets. Inf. Comput. 253(Pt. 3), 399\u2013410 (2017)","journal-title":"Inf. Comput."},{"key":"310_CR15","unstructured":"Best, E., Devillers, R.: Petri net pre-synthesis based on prime cycles and distance paths. To appear in Science of Computer Programming (2018). Also: Informatik-Bericht Nr. 3\/16, Univ. Oldenburg, 26 pages (2016)"},{"key":"310_CR16","unstructured":"Caillaud, B.: Synet: un outil de synth\u00e8se de r\u00e9saux de Petri born\u00e9s, applications. Research Report RR 3155, INRIA (1997). See also: https:\/\/hal.inria.fr\/inria-00073534 . http:\/\/www.irisa.fr\/s4\/tools\/synet\/"},{"key":"310_CR17","first-page":"1","volume-title":"Transactions on Petri Nets and Other Models of Concurrency VI, Lecture Notes in Computer Science","author":"J Carmona","year":"2012","unstructured":"Carmona, J.: The label splitting problem. In: Jensen, K., Aalst, W.M.V.D., Ajmone-Marsan, M., Franceschinis, G., Kleijn, J., Kristensen, L.M. (eds.) Transactions on Petri Nets and Other Models of Concurrency VI, Lecture Notes in Computer Science, vol. 7400, pp. 1\u201323. Springer, Berlin (2012)"},{"key":"310_CR18","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1007\/978-3-540-68746-7_10","volume-title":"Applications and Theory of Petri Nets 2008, LNCS","author":"J Carmona","year":"2008","unstructured":"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, K., Valk, R. (eds.) Applications and Theory of Petri Nets 2008, LNCS, vol. 5062, pp. 92\u2013111. Springer, Berlin (2008)"},{"issue":"3","key":"310_CR19","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1109\/TC.2009.131","volume":"59","author":"J Carmona","year":"2010","unstructured":"Carmona, J., Cortadella, J., Kishinevsky, M.: New region-based algorithms for deriving bounded Petri nets. IEEE Trans. Comput. 59(3), 371\u2013384 (2010)","journal-title":"IEEE Trans. Comput."},{"issue":"5","key":"310_CR20","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1016\/S0022-0000(71)80013-2","volume":"5","author":"F Commoner","year":"1971","unstructured":"Commoner, F., Holt, A.W., Even, S., Pnueli, A.: Marked directed graphs. J. Comput. Syst. Sci. 5(5), 511\u2013523 (1971)","journal-title":"J. Comput. Syst. Sci."},{"key":"310_CR21","unstructured":"Christ, J., Hoenicke, J., Nutz, A.: SMTInterpol: an interpolating SMT solver. In: Donaldson, A., Parker, D. (eds.) Proc. of Model Checking Software, Oxford, LNCS, vol. 7385, pp. 248\u2013254. Springer, Berlin (2012). See also: https:\/\/ultimate.informatik.uni-freiburg.de\/smtinterpol\/"},{"issue":"3","key":"310_CR22","first-page":"315","volume":"E80\u2013D","author":"J Cortadella","year":"1997","unstructured":"Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Petrify: a tool for manipulating concurrent specifications and synthesis of asynchronous controllers. IEICE Trans. Inf. Syst. E80\u2013D(3), 315\u2013325 (1997)","journal-title":"IEICE Trans. Inf. Syst."},{"issue":"8","key":"310_CR23","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1109\/12.707587","volume":"47","author":"J Cortadella","year":"1998","unstructured":"Cortadella, J., Kishinevsky, M., Lavagno, L., Yakovlev, A.: Deriving Petri nets for finite transition systems. IEEE Trans. Comput. 47(8), 859\u2013882 (1998)","journal-title":"IEEE Trans. Comput."},{"key":"310_CR24","volume-title":"Logic Synthesis for Asynchronous Controllers and Interfaces, Volume 8 of Advanced Microelectronics","author":"J Cortadella","year":"2012","unstructured":"Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Logic Synthesis for Asynchronous Controllers and Interfaces, Volume 8 of Advanced Microelectronics. Springer Science & Business Media, Berlin (2012)"},{"issue":"3","key":"310_CR25","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/0020-0190(75)90020-4","volume":"3","author":"S Crespi-Reghizzi","year":"1975","unstructured":"Crespi-Reghizzi, S., Mandrioli, D.: A decidability theorem for a class of vector-addition systems. Inf. Process. Lett. 3(3), 78\u201380 (1975)","journal-title":"Inf. Process. Lett."},{"key":"310_CR26","doi-asserted-by":"crossref","unstructured":"de San Pedro, J., Cortadella, J.: Mining structured Petri nets for the visualization of process behavior. In: 31st ACM Symposium on Applied Computing, pp. 839\u2013846, Pisa (2016)","DOI":"10.1145\/2851613.2851645"},{"key":"310_CR27","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1017\/CBO9780511526558","volume-title":"Free Choice Petri Nets","author":"J Desel","year":"1995","unstructured":"Desel, J., Esparza, J.: Free Choice Petri Nets, vol. 40, p. 242. Cambridge Tracts in Theoretical Computer Science, Cambridge (1995)"},{"issue":"2","key":"310_CR28","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF00289519","volume":"1","author":"EW Dijkstra","year":"1971","unstructured":"Dijkstra, E.W.: Hierarchical ordering of sequential processes. Acta Inf. 1(2), 115\u2013138 (1971)","journal-title":"Acta Inf."},{"issue":"4","key":"310_CR29","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF00264611","volume":"27","author":"A Ehrenfeucht","year":"1990","unstructured":"Ehrenfeucht, A., Rozenberg, G.: Partial 2-structures, part I: basic notions and the representation problem, and part II: state spaces of concurrent systems. Acta Inf. 27(4), 315\u2013368 (1990)","journal-title":"Acta Inf."},{"key":"310_CR30","unstructured":"Erofeev, E., Barylska, K., Mikulski, \u0141., Pi\u0105tkowski, M.: Generating all minimal Petri net unsolvable binary words. In: Proceedings of the Prague Stringology Conference, pp. 33\u201346 (2016). See http:\/\/www.stringology.org\/event\/"},{"key":"310_CR31","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BFb0019974","volume-title":"Advances of Petri Nets 1991, LNCS","author":"RP Hopkins","year":"1991","unstructured":"Hopkins, R.P.: Distributable nets. Applications and theory of Petri nets 1990. In: Rozenberg, G. (ed.) Advances of Petri Nets 1991, LNCS, vol. 524, pp. 161\u2013187. Springer, Berlin (1991)"},{"key":"310_CR32","doi-asserted-by":"crossref","unstructured":"Keller, R.M.: A fundamental theorem of asynchronous parallel computation. In: Parallel Processing, LNCS, vol. 24, pp. 102\u2013112. Springer, Berlin (1975)","DOI":"10.1007\/3-540-07135-0_113"},{"key":"310_CR33","unstructured":"Khachiyan, L.: Selected works. Moscow Center for Mathematical Continuous Education. ISBN 978-5-94057-509-2, 519 pages (2009) (in Russian)"},{"key":"310_CR34","doi-asserted-by":"crossref","unstructured":"Kondratyev, A., Cortadella, J., Kishinevsky, M., Pastor, E., Roig, O., Yakovlev, A.: Checking signal transition graph implementability by symbolic BDD traversal. In: Proc. European Design and Test Conference, pp. 325\u2013332, Paris (1995)","DOI":"10.1109\/EDTC.1995.470376"},{"issue":"3","key":"310_CR35","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1145\/322077.322079","volume":"25","author":"LH Landweber","year":"1978","unstructured":"Landweber, L.H., Robertson, E.L.: Properties of conflict-free and persistent Petri nets. JACM 25(3), 352\u2013364 (1978)","journal-title":"JACM"},{"key":"310_CR36","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1109\/5.24143","volume":"77","author":"T Murata","year":"1989","unstructured":"Murata, T.: Petri nets: properties, analysis and applications. Proc. IEEE 77, 541\u2013580 (1989)","journal-title":"Proc. IEEE"},{"key":"310_CR37","first-page":"251","volume-title":"Proc. of the Advanced Course on General Net Theory of Processes and Systems, Hamburg, LNCS","author":"CA Petri","year":"1980","unstructured":"Petri, C.A.: Concurrency. In: Brauer, W. (ed.) Proc. of the Advanced Course on General Net Theory of Processes and Systems, Hamburg, LNCS, vol. 84, pp. 251\u2013260. Springer, Berlin (1980)"},{"key":"310_CR38","volume-title":"Petri Nets. EATCS Monographs on Theoretical Computer Science","author":"W Reisig","year":"1985","unstructured":"Reisig, W.: Petri Nets. EATCS Monographs on Theoretical Computer Science, vol. 4. Springer, Berlin (1985)"},{"key":"310_CR39","unstructured":"Schlachter, U. et al.: https:\/\/github.com\/CvO-Theory\/apt (2013\u20132017)"},{"key":"310_CR40","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1109\/3468.553226","volume":"27\u20131","author":"E Teruel","year":"1997","unstructured":"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\u20131, 73\u201383 (1997)","journal-title":"IEEE Trans. Syst. Man Cybern. Part A"},{"key":"310_CR41","doi-asserted-by":"crossref","unstructured":"van Glabbeek, R.J., Goltz, U., Schicke-Uffmann, J.-W.: On distributability of Petri nets\u2014(extended abstract). In: Birkedal, L. (ed.) Proc. FoSSaCS 2012 (Held as Part of ETAPS), LNCS, vol. 7213, pp. 331\u2013345. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-28729-9_22"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-017-0310-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-017-0310-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-017-0310-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T04:43:17Z","timestamp":1750999397000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-017-0310-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,20]]},"references-count":41,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["310"],"URL":"https:\/\/doi.org\/10.1007\/s00236-017-0310-9","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11,20]]}}}