论文标题
关于使布尔网可实现的过渡系统的复杂性
On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets
论文作者
论文摘要
综合包括确定给定标记的过渡系统（TS）$ a $是否可以由类型$τ$的净$ n $实现。如果做出负面决定，则可以通过应用各种修改技术（例如先前具有相同标签，抑制边缘/状态/事件等的重新标签边缘）来将$ a $转换为可实现的TS $ b $。但是，它可能会限制此类修改的数量以保持接近原始问题或优化技术。在本文中，我们表明，如果$τ$对应于触发器网的类型或某些触发器网络衍生物，则大多数相应的问题都是NP填充。
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.
