{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T20:29:04Z","timestamp":1760300944064,"version":"3.40.3"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030642754"},{"type":"electronic","value":"9783030642761"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-64276-1_8","type":"book-chapter","created":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T07:04:38Z","timestamp":1606201478000},"page":"143-160","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Occupancy Number Restricted Boolean Petri Net Synthesis: A Fixed-Parameter Algorithm"],"prefix":"10.1007","author":[{"given":"Evgeny","family":"Erofeev","sequence":"first","affiliation":[]},{"given":"Ronny","family":"Tredup","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,11,25]]},"reference":[{"key":"8_CR1","series-title":"Discovery, Conformance and Enhancement of Business Processes","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19345-3","volume-title":"Process Mining","author":"WMP van der Aalst","year":"2011","unstructured":"van der Aalst, W.M.P.: Process Mining. Discovery, Conformance and Enhancement of Business Processes. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-19345-3"},{"issue":"1\u20132","key":"8_CR2","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0304-3975(96)00219-8","volume":"186","author":"E Badouel","year":"1997","unstructured":"Badouel, E., Bernardinello, L., Darondeau, P.: The synthesis problem for elementary net systems is NP-complete. Theor. Comput. Sci. 186(1\u20132), 107\u2013134 (1997). https:\/\/doi.org\/10.1016\/S0304-3975(96)00219-8","journal-title":"Theor. Comput. Sci."},{"key":"8_CR3","series-title":"Texts in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47967-4","volume-title":"Petri Net Synthesis","author":"E Badouel","year":"2015","unstructured":"Badouel, E., Bernardinello, L., Darondeau, P.: Petri Net Synthesis. TTCSAES. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47967-4"},{"issue":"7","key":"8_CR4","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1007\/BF01186645","volume":"32","author":"E Badouel","year":"1995","unstructured":"Badouel, E., Darondeau, P.: Trace nets and process automata. Acta Inf. 32(7), 647\u2013679 (1995). https:\/\/doi.org\/10.1007\/BF01186645","journal-title":"Acta Inf."},{"key":"8_CR5","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2012.04.046","volume":"449","author":"P Baldan","year":"2012","unstructured":"Baldan, P., Bruni, A., Corradini, A., K\u00f6nig, B., Rodr\u00edguez, C., Schwoon, S.: Efficient unfolding of contextual Petri nets. Theor. Comput. Sci. 449, 2\u201322 (2012). https:\/\/doi.org\/10.1016\/j.tcs.2012.04.046. http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397512004318, descriptional Complexity of Formal Systems (DCFS 2011)","journal-title":"Theor. Comput. Sci."},{"key":"8_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/978-3-319-04921-2_13","volume-title":"Language and Automata Theory and Applications","author":"E Best","year":"2014","unstructured":"Best, E., Devillers, R.: Characterisation of the state spaces of live and bounded marked graph Petri nets. In: Dediu, A.-H., Mart\u00edn-Vide, C., Sierra-Rodr\u00edguez, J.-L., Truthe, B. (eds.) LATA 2014. LNCS, vol. 8370, pp. 161\u2013172. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-04921-2_13"},{"key":"8_CR7","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.tcs.2017.10.006","volume":"750","author":"E Best","year":"2018","unstructured":"Best, E., Hujsa, T., Wimmel, H.: Sufficient conditions for the marked graph realisability of labelled transition systems. Theor. Comput. Sci. 750, 101\u2013116 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2017.10.006","journal-title":"Theor. Comput. Sci."},{"key":"8_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1007\/978-3-540-85758-7_26","volume-title":"Business Process Management","author":"J Carmona","year":"2008","unstructured":"Carmona, J., 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\u2013373. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-85758-7_26"},{"issue":"1","key":"8_CR9","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s11047-019-09748-4","volume":"19","author":"T Chatain","year":"2020","unstructured":"Chatain, T., Haar, S., Kolc\u00e1k, J., Paulev\u00e9, L., Thakkar, A.: Concurrency in Boolean networks. Nat. Comput. 19(1), 91\u2013109 (2020). https:\/\/doi.org\/10.1007\/s11047-019-09748-4","journal-title":"Nat. Comput."},{"key":"8_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55989-1","volume-title":"Logic Synthesis of Asynchronous Controllers and Interfaces","author":"J Cortadella","year":"2002","unstructured":"Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Logic Synthesis of Asynchronous Controllers and Interfaces, vol. 8. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/978-3-642-55989-1"},{"key":"8_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"8_CR12","unstructured":"Devillers, R.R., Erofeev, E., Hujsa, T.: Synthesis of weighted marked graphs from circular labelled transition systems. In: van der Aalst, W.M.P., Bergenthum, R., Carmona, J. (eds.) ATAED@Petri Nets\/ACSD 2019, Aachen, Germany, June 25, 2019. CEUR Workshop Proceedings, vol. 2371, pp. 6\u201322. CEUR-WS.org (2019). http:\/\/ceur-ws.org\/Vol-2371\/ATAED2019-6-22.pdf"},{"key":"8_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-662-60651-3_7","volume-title":"Transactions on Petri Nets and Other Models of Concurrency XIV","author":"R Devillers","year":"2019","unstructured":"Devillers, R., Erofeev, E., Hujsa, T.: Synthesis of weighted marked graphs from constrained labelled transition systems: a geometric approach. In: Koutny, M., Pomello, L., Kristensen, L.M. (eds.) Transactions on Petri Nets and Other Models of Concurrency XIV. LNCS, vol. 11790, pp. 172\u2013191. Springer, Heidelberg (2019). https:\/\/doi.org\/10.1007\/978-3-662-60651-3_7"},{"key":"8_CR14","unstructured":"Erofeev, E.: Characterisation of a class of Petri net solvable transition systems. Ph.D. thesis, University of Oldenburg, Germany (2018)"},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1109\/TSE.1978.233859","volume":"SE\u20134","author":"T Gannon","year":"1978","unstructured":"Gannon, T., Shapiro, S.: An optimal approach to fault tolerant software systems design. IEEE Trans. Softw. Eng. SE\u20134, 390\u2013409 (1978). https:\/\/doi.org\/10.1109\/TSE.1978.233859","journal-title":"IEEE Trans. Softw. Eng."},{"key":"8_CR16","doi-asserted-by":"publisher","unstructured":"Lorenz, R., Mauser, S., Juhas, G.: How to synthesize nets from languages - a survey, pp. 637\u2013647 (January 2008). https:\/\/doi.org\/10.1109\/WSC.2007.4419657","DOI":"10.1109\/WSC.2007.4419657"},{"key":"8_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/3-540-57787-4_18","volume-title":"Graph Transformations in Computer Science","author":"U Montanari","year":"1994","unstructured":"Montanari, U., Rossi, F.: Contextual occurrence nets and concurrent constraint programming. In: Schneider, H.J., Ehrig, H. (eds.) Graph Transformations in Computer Science. LNCS, vol. 776, pp. 280\u2013295. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/3-540-57787-4_18"},{"issue":"6","key":"8_CR18","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/BF01178907","volume":"32","author":"U Montanari","year":"1995","unstructured":"Montanari, U., Rossi, F.: Contextual nets. Acta Inf. 32(6), 545\u2013596 (1995). https:\/\/doi.org\/10.1007\/BF01178907","journal-title":"Acta Inf."},{"key":"8_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/3-540-63139-9_43","volume-title":"Application and Theory of Petri Nets 1997","author":"M Pietkiewicz-Koutny","year":"1997","unstructured":"Pietkiewicz-Koutny, M.: Transition systems of elementary net systems with inhibitor arcs. In: Az\u00e9ma, P., Balbo, G. (eds.) ICATPN 1997. LNCS, vol. 1248, pp. 310\u2013327. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-63139-9_43"},{"key":"8_CR20","unstructured":"Institute for Quality, Safety and Transportation: $$\\pi $$-tool (2013). http:\/\/www.iqst.de"},{"key":"8_CR21","doi-asserted-by":"publisher","unstructured":"Schlachter, U.: Bounded Petri net synthesis from modal transition systems is undecidable. In: Desharnais, J., Jagadeesan, R. (eds.) 27th International Conference on Concurrency Theory, CONCUR 2016, August 23\u201326, 2016, Qu\u00e9bec City, Canada. LIPIcs, vol. 59, pp. 15:1\u201315:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2016.15","DOI":"10.4230\/LIPIcs.CONCUR.2016.15"},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"Schlachter, U.: Petri net synthesis and modal specifications. Ph.D. thesis, University of Oldenburg, Germany (2018)","DOI":"10.7561\/SACS.2018.2.199"},{"key":"8_CR23","doi-asserted-by":"publisher","unstructured":"Schlachter, U., Wimmel, H.: k-bounded Petri net synthesis from modal transition systems. In: CONCUR. LIPIcs, vol. 85, pp. 6:1\u20136:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2017.6","DOI":"10.4230\/LIPIcs.CONCUR.2017.6"},{"key":"8_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/3-540-60922-9_42","volume-title":"STACS 96","author":"V Schmitt","year":"1996","unstructured":"Schmitt, V.: Flip-flop nets. In: Puech, C., Reischuk, R. (eds.) STACS 1996. LNCS, vol. 1046, pp. 515\u2013528. Springer, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-60922-9_42"},{"issue":"4","key":"8_CR25","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1002\/net.3230090407","volume":"9","author":"S Shapiro","year":"1979","unstructured":"Shapiro, S.: A stochastic Petri net with applications to modelling occupancy times for concurrent task systems. Networks 9(4), 375\u2013379 (1979). https:\/\/doi.org\/10.1002\/net.3230090407","journal-title":"Networks"},{"key":"8_CR26","unstructured":"Tredup, R.: The complexity of synthesizing nop-equipped Boolean nets from g-bounded inputs (technical report) (2019)"},{"key":"8_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/978-3-030-30806-3_16","volume-title":"Reachability Problems","author":"R Tredup","year":"2019","unstructured":"Tredup, R.: Synthesis of structurally restricted b-bounded Petri nets: complexity results. In: Filiot, E., Jungers, R., Potapov, I. (eds.) RP 2019. LNCS, vol. 11674, pp. 202\u2013217. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-30806-3_16"},{"key":"8_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/978-3-030-38919-2_19","volume-title":"SOFSEM 2020: Theory and Practice of Computer Science","author":"R Tredup","year":"2020","unstructured":"Tredup, R.: Parameterized complexity of synthesizing b-bounded (m,\u00a0n)-T-systems. In: Chatzigeorgiou, A., et al. (eds.) SOFSEM 2020. LNCS, vol. 12011, pp. 223\u2013235. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-38919-2_19"},{"key":"8_CR29","doi-asserted-by":"publisher","unstructured":"Tredup, R., Erofeev, E.: On the parameterized complexity of d-restricted Boolean net synthesis. In: Chen, J., Feng, Q., Xu, J. (eds.) Theory and Applications of Models of Computation. TAMC 2020. Lecture Notes in Computer Science, vol. 12337. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-59267-7_20","DOI":"10.1007\/978-3-030-59267-7_20"},{"key":"8_CR30","doi-asserted-by":"publisher","unstructured":"Tredup, R., Rosenke, C.: Narrowing down the hardness barrier of synthesizing elementary net systems. In: CONCUR. LIPIcs, vol. 118, pp. 16:1\u201316:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2018.16","DOI":"10.4230\/LIPIcs.CONCUR.2018.16"},{"key":"8_CR31","doi-asserted-by":"publisher","unstructured":"Tredup, R., Rosenke, C.: The complexity of synthesis for 43 boolean petri net types. In: Gopal, T.V., Watada, J. (eds.) TAMC 2019. LNCS, vol. 11436, pp. 615\u2013634. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-14812-6_38","DOI":"10.1007\/978-3-030-14812-6_38"},{"key":"8_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-319-91268-4_3","volume-title":"Application and Theory of Petri Nets and Concurrency","author":"R Tredup","year":"2018","unstructured":"Tredup, R., Rosenke, C., Wolf, K.: Elementary net synthesis remains NP-complete even for extremely simple inputs. In: Khomenko, V., Roux, O.H. (eds.) PETRI NETS 2018. LNCS, vol. 10877, pp. 40\u201359. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-91268-4_3"},{"key":"8_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/BFb0055644","volume-title":"CONCUR 1998 Concurrency Theory","author":"W Vogler","year":"1998","unstructured":"Vogler, W., Semenov, A., Yakovlev, A.: Unfolding and finite prefix for nets with read arcs. In: Sangiorgi, D., de Simone, R. (eds.) CONCUR 1998. LNCS, vol. 1466, pp. 501\u2013516. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0055644"}],"container-title":["Lecture Notes in Computer Science","Theoretical Aspects of Computing \u2013 ICTAC 2020"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-64276-1_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,24]],"date-time":"2021-04-24T01:34:16Z","timestamp":1619228056000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-64276-1_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030642754","9783030642761"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-64276-1_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"25 November 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ICTAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Colloquium on Theoretical Aspects of Computing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Macau","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 November 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 December 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ictac2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ictac2020.github.io\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"40","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"15","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"38% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was planned to take place in Macau, China, and changed to a virtual format due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}