{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T14:27:28Z","timestamp":1777645648402,"version":"3.51.4"},"reference-count":0,"publisher":"SAGE Publications","issue":"3-4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["FI"],"published-print":{"date-parts":[[2023,10,26]]},"abstract":"<jats:p>Let us consider some class of (Petri) nets. The corresponding Synthesis problem consists in deciding whether a given labeled transition system (TS) A can be implemented by a net N of that class. In case of a negative decision, it may be possible to convert A into an implementable TS B by applying various modification techniques, like relabeling edges that previously had the same label, suppressing edges\/states\/events, etc. It may however be useful to limit the number of such modifications to stay close to the original problem, or optimize the technique. In this paper, we show that most of the corresponding problems are NP-complete if the considered class corresponds to so-called flip-flop nets or some flip-flop net derivatives.<\/jats:p>","DOI":"10.3233\/fi-222161","type":"journal-article","created":{"date-parts":[[2023,10,27]],"date-time":"2023-10-27T11:15:57Z","timestamp":1698405357000},"page":"261-296","source":"Crossref","is-referenced-by-count":0,"title":["On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets"],"prefix":"10.1177","volume":"189","author":[{"given":"Raymond","family":"Devillers","sequence":"first","affiliation":[{"name":"D\u00e9partement d\u2019Informatique, Universit\u00e9 Libre de Bruxelles, Boulevard du Triomphe, C.P. 212, B-1050 Bruxelles, Belgium. raymond.devillersl@ulb.be"}]},{"given":"Ronny","family":"Tredup","sequence":"additional","affiliation":[{"name":"Geschwister-Scholl-Gymnasium L\u00f6bau, Pestalozzistra\u00dfe 21, 02708 L\u00f6bau Germany. tredupron@gsg-loebau.lernsax.de"}]}],"member":"179","container-title":["Fundamenta Informaticae"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/FI-222161","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T06:32:52Z","timestamp":1777444372000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/FI-222161"}},"subtitle":[],"editor":[{"given":"Paul C.","family":"Bell","sequence":"additional","affiliation":[]},{"given":"Igor","family":"Potapov","sequence":"additional","affiliation":[]},{"given":"Sylvain","family":"Schmitz","sequence":"additional","affiliation":[]},{"given":"Patrick","family":"Totzke","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2023,10,26]]},"references-count":0,"journal-issue":{"issue":"3-4"},"URL":"https:\/\/doi.org\/10.3233\/fi-222161","relation":{},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"value":"0169-2968","type":"print"},{"value":"1875-8681","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,26]]}}}