On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets

Synthesis consists in deciding whether a given labeled transition system (TS)$A$ can be implemented by a net $N$ of type $\tau$. In case of a negativedecision, it may be possible to convert $A$ into an implementable TS $B$ byapplying various modification techniques, like relabeling edges that previouslyhad the same label, suppressing edges/states/events, etc. It may however beuseful to limit the number of such modifications to stay close to the originalproblem, or optimize the technique. In this paper, we show that most of thecorresponding problems are NP-complete if $\tau$ corresponds to the type offlip-flop nets or some flip-flop net derivatives