On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets
For researchers in synthesis and net theory, this establishes computational hardness for optimizing modifications to achieve implementability.
The paper shows that problems of modifying labeled transition systems to make them implementable by flip-flop nets or their derivatives are NP-complete, limiting the feasibility of such modifications.
Synthesis consists in deciding whether a given labeled transition system (TS) $A$ can be implemented by a net $N$ of type $Ï$. 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 $Ï$ corresponds to the type of flip-flop nets or some flip-flop net derivatives.