{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T06:03:57Z","timestamp":1743141837172,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030617387"},{"type":"electronic","value":"9783030617394"}],"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-61739-4_10","type":"book-chapter","created":{"date-parts":[[2020,10,14]],"date-time":"2020-10-14T23:14:46Z","timestamp":1602717286000},"page":"148-163","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of the Label-Splitting-Problem for Flip-Flop-Nets"],"prefix":"10.1007","author":[{"given":"Ronny","family":"Tredup","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,10,15]]},"reference":[{"key":"10_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19345-3","volume-title":"Process Mining - Discovery, Conformance and Enhancement of Business Processes","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"},{"key":"10_CR2","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 \u201995: 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":"10_CR3","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. Theoret. Comput. Sci. 186(1\u20132), 107\u2013134 (1997). https:\/\/doi.org\/10.1016\/S0304-3975(96)00219-8","journal-title":"Theoret. Comput. Sci."},{"key":"10_CR4","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":"6","key":"10_CR5","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/s001650200022","volume":"13","author":"E Badouel","year":"2002","unstructured":"Badouel, E., Caillaud, B., Darondeau, P.: Distributing finite automata through Petri net synthesis. Formal Asp. Comput. 13(6), 447\u2013470 (2002). https:\/\/doi.org\/10.1007\/s001650200022","journal-title":"Formal Asp. Comput."},{"issue":"7","key":"10_CR6","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 Informatica 32(7), 647\u2013679 (1995). https:\/\/doi.org\/10.1007\/BF01186645","journal-title":"Acta Informatica"},{"key":"10_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-35179-2_1","volume-title":"Transactions on Petri Nets and Other Models of Concurrency VI","author":"J Carmona","year":"2012","unstructured":"Carmona, J.: The label splitting problem. In: Jensen, K., van der Aalst, W.M., Ajmone Marsan, M., Franceschinis, G., Kleijn, J., Kristensen, L.M. (eds.) Transactions on Petri Nets and Other Models of Concurrency VI. LNCS, vol. 7400, pp. 1\u201323. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-35179-2_1"},{"issue":"8","key":"10_CR8","doi-asserted-by":"publisher","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 from finite transition systems. IEEE Trans. Comput. 47(8), 859\u2013882 (1998)","journal-title":"IEEE Trans. Comput."},{"issue":"8","key":"10_CR9","doi-asserted-by":"publisher","first-page":"793","DOI":"10.1109\/43.644602","volume":"16","author":"J Cortadella","year":"1997","unstructured":"Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: A region-based theory for state assignment in speed-independent circuits. IEEE Trans. CAD Integr. Circuits Syst. 16(8), 793\u2013812 (1997). https:\/\/doi.org\/10.1109\/43.644602","journal-title":"IEEE Trans. CAD Integr. Circuits Syst."},{"key":"10_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"issue":"2","key":"10_CR11","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1023\/A:1008271916548","volume":"7","author":"LE Holloway","year":"1997","unstructured":"Holloway, L.E., Krogh, B.H., Giua, A.: A survey of Petri net methods for controlled discrete event systems. Discrete Event Dyn. Syst. 7(2), 151\u2013190 (1997). https:\/\/doi.org\/10.1023\/A:1008271916548","journal-title":"Discrete Event Dyn. Syst."},{"issue":"1","key":"10_CR12","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 Informatica 50(1), 15\u201339 (2013). https:\/\/doi.org\/10.1007\/s00236-012-0170-2","journal-title":"Acta Informatica"},{"issue":"6","key":"10_CR13","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 Informatica 32(6), 545\u2013596 (1995). https:\/\/doi.org\/10.1007\/BF01178907","journal-title":"Acta Informatica"},{"key":"10_CR14","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":"10_CR15","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":"10_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/978-3-662-60651-3_9","volume-title":"Transactions on Petri Nets and Other Models of Concurrency XIV","author":"U Schlachter","year":"2019","unstructured":"Schlachter, U., Wimmel, H.: Relabelling LTS for Petri net synthesis via solving separation problems. In: Koutny, M., Pomello, L., Kristensen, L.M. (eds.) Transactions on Petri Nets and Other Models of Concurrency XIV. LNCS, vol. 11790, pp. 222\u2013254. Springer, Heidelberg (2019). https:\/\/doi.org\/10.1007\/978-3-662-60651-3_9"},{"key":"10_CR17","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":"10_CR18","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"},{"key":"10_CR19","unstructured":"Tredup, R.: The complexity of synthesizing nop-equipped Boolean nets from g-bounded inputs. Technical report (2019)"},{"key":"10_CR20","unstructured":"Tredup, R.: Finding an optimal label-splitting to make a transition system petri net implementable: a complete complexity characterization. In: Italian Conference on Theoretical Computer Science - 21st Annual Conference, ICTCS 2020 (2020, to appear )"},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"Tredup, R., Erofeev, E.: The complexity of Boolean state separation (2020). Submitted to ICTAC 2020 (2020)","DOI":"10.1007\/978-3-030-64276-1_7"},{"key":"10_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-14812-6","volume-title":"Theory and Applications of Models of Computation","year":"2019","unstructured":"Gopal, T.V., Watada, J. (eds.): TAMC 2019. LNCS, vol. 11436. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-14812-6"},{"key":"10_CR23","unstructured":"Tredup, R., Rosenke, C.: On the hardness of synthesizing Boolean nets. In: ATAED@Petri Nets\/ACSD. CEUR Workshop Proceedings, vol. 2371, pp. 71\u201386 (2019). CEUR-WS.org"}],"container-title":["Lecture Notes in Computer Science","Reachability Problems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-61739-4_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,8]],"date-time":"2021-04-08T21:24:25Z","timestamp":1617917065000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-61739-4_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030617387","9783030617394"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-61739-4_10","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":"15 October 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"RP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Reachability Problems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paris","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","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":"19 October 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 October 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"rp2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.irif.fr\/~rp2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}