Raymond Devillers ; Ronny Tredup
-
On the Complexity of Techniques That Make Transition Systems
Implementable by Boolean Nets
fi:9231 -
Fundamenta Informaticae,
October 14, 2023,
Volume 189, Issues 3-4: Reachability Problems 2020 and 2021
On the Complexity of Techniques That Make Transition Systems
Implementable by Boolean NetsArticle
Authors: Raymond Devillers ; Ronny Tredup
NULL##NULL
Raymond Devillers;Ronny Tredup
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.