{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T00:00:45Z","timestamp":1743033645699,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"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_7","type":"book-chapter","created":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T07:04:38Z","timestamp":1606201478000},"page":"123-142","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The Complexity of Boolean State Separation"],"prefix":"10.1007","author":[{"given":"Ronny","family":"Tredup","sequence":"first","affiliation":[]},{"given":"Evgeny","family":"Erofeev","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,11,25]]},"reference":[{"key":"7_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/3-540-59293-8_207","volume-title":"TAPSOFT 1995: Theory and Practice of Software Development","author":"E Badouel","year":"1995","unstructured":"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\u2013378. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-59293-8_207"},{"issue":"1\u20132","key":"7_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":"7_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":"7_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":"7_CR5","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.scico.2017.07.005","volume":"157","author":"E Best","year":"2018","unstructured":"Best, E., Devillers, R.R.: Pre-synthesis of Petri nets based on prime cycles and distance paths. Sci. Comput. Program. 157, 41\u201355 (2018). https:\/\/doi.org\/10.1016\/j.scico.2017.07.005","journal-title":"Sci. Comput. Program."},{"issue":"1","key":"7_CR6","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":"7_CR7","first-page":"244","volume":"52","author":"J Esparza","year":"1994","unstructured":"Esparza, J., Nielsen, M.: Decidability issues for Petri nets - a survey. Bull. EATCS 52, 244\u2013262 (1994)","journal-title":"Bull. EATCS"},{"issue":"1","key":"7_CR8","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/s00236-012-0170-2","volume":"50","author":"J Kleijn","year":"2013","unstructured":"Kleijn, J., Koutny, M., Pietkiewicz-Koutny, M., Rozenberg, G.: Step semantics of Boolean nets. Acta Inf. 50(1), 15\u201339 (2013). https:\/\/doi.org\/10.1007\/s00236-012-0170-2","journal-title":"Acta Inf."},{"key":"7_CR9","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":"7_CR10","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."},{"issue":"4","key":"7_CR11","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/s00454-001-0047-6","volume":"26","author":"C Moore","year":"2001","unstructured":"Moore, C., Robson, J.M.: Hard tiling problems with simple tiles. Discret. Comput. Geom. 26(4), 573\u2013590 (2001). https:\/\/doi.org\/10.1007\/s00454-001-0047-6","journal-title":"Discret. Comput. Geom."},{"key":"7_CR12","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":"7_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1007\/3-540-65306-6_14","volume-title":"Lectures on Petri Nets I: Basic Models","author":"G Rozenberg","year":"1998","unstructured":"Rozenberg, G., Engelfriet, J.: Elementary net systems. In: Reisig, W., Rozenberg, G. (eds.) ACPN 1996. LNCS, vol. 1491, pp. 12\u2013121. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/3-540-65306-6_14"},{"key":"7_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1007\/978-3-319-77313-1_23","volume-title":"Language and Automata Theory and Applications","author":"U Schlachter","year":"2018","unstructured":"Schlachter, U.: Over-approximative Petri net synthesis for restricted subclasses of nets. In: Klein, S.T., Mart\u00edn-Vide, C., Shapira, D. (eds.) LATA 2018. LNCS, vol. 10792, pp. 296\u2013307. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-77313-1_23"},{"unstructured":"Schlachter, U., Wimmel, H.: Optimal label splitting for embedding an LTS into an arbitrary Petri net reachability graph is NP-complete. CoRR abs\/2002.04841 (2020). https:\/\/arxiv.org\/abs\/2002.04841","key":"7_CR15"},{"key":"7_CR16","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"},{"unstructured":"Tredup, R.: The complexity of synthesizing nop-equipped Boolean nets from g-bounded inputs (technical report) (2019)","key":"7_CR17"},{"key":"7_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/978-3-030-21571-2_10","volume-title":"Application and Theory of Petri Nets and Concurrency","author":"R Tredup","year":"2019","unstructured":"Tredup, R.: Fixed parameter tractability and polynomial time results for the synthesis of b-bounded Petri nets. In: Donatelli, S., Haar, S. (eds.) PETRI NETS 2019. LNCS, vol. 11522, pp. 148\u2013168. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-21571-2_10"},{"key":"7_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-030-21571-2_9","volume-title":"Application and Theory of Petri Nets and Concurrency","author":"R Tredup","year":"2019","unstructured":"Tredup, R.: Hardness results for the synthesis of b-bounded Petri nets. In: Donatelli, S., Haar, S. (eds.) PETRI NETS 2019. LNCS, vol. 11522, pp. 127\u2013147. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-21571-2_9"},{"key":"7_CR20","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"},{"doi-asserted-by":"crossref","unstructured":"Tredup, R., Erofeev, E.: The complexity of Boolean state separation (technical report) (2020). submitted to arxive.org","key":"7_CR21","DOI":"10.1007\/978-3-030-64276-1_7"},{"unstructured":"Tredup, R., Erofeev, E.: On the complexity of synthesis of nop-free Boolean Petri nets. In: van der Aalst, W.M.P., Bergenthum, R., Carmona, J. (eds.) Proceedings of the International Workshop on Algorithms & Theories for the Analysis of Event Data 2020 Satellite event of the 41st International Conference on Application and Theory of Petri Nets and Concurrency Petri Nets 2020, Virtual Workshop, June 24, 2020. CEUR Workshop Proceedings, vol. 2625, pp. 66\u201384. CEUR-WS.org (2020). http:\/\/ceur-ws.org\/Vol-2625\/paper-05.pdf","key":"7_CR22"},{"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","key":"7_CR23","DOI":"10.1007\/978-3-030-14812-6_38"},{"key":"7_CR24","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":"7_CR25","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"},{"key":"7_CR26","doi-asserted-by":"publisher","first-page":"104482","DOI":"10.1016\/j.ic.2019.104482","volume":"271","author":"H Wimmel","year":"2020","unstructured":"Wimmel, H.: Presynthesis of bounded choice-free or fork-attribution nets. Inf. Comput. 271, 104482 (2020)","journal-title":"Inf. Comput."},{"issue":"3","key":"7_CR27","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/S0167-9260(96)00010-7","volume":"21","author":"A Yakovlev","year":"1996","unstructured":"Yakovlev, A., Koelmans, A., Semenov, A.L., Kinniment, D.J.: Modelling, analysis and synthesis of asynchronous control circuits using Petri nets. Integration 21(3), 143\u2013170 (1996). https:\/\/doi.org\/10.1016\/S0167-9260(96)00010-7","journal-title":"Integration"}],"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_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,24]],"date-time":"2021-04-24T01:34:37Z","timestamp":1619228077000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-64276-1_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030642754","9783030642761"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-64276-1_7","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)"}}]}}