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

    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 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 $\tau$ corresponds to the type of flip-flop nets or some flip-flop net derivatives.


    Volume: Volume 189, Issues 3-4: Reachability Problems 2020 and 2021
    Published on: October 14, 2023
    Accepted on: March 8, 2023
    Submitted on: March 20, 2022
    Keywords: Computer Science - Computational Complexity

    Consultation statistics

    This page has been seen 47 times.
    This article's PDF has been downloaded 21 times.