论文标题
关于依赖性限制的合成布尔培养皿网的参数化复杂性
On the Parameterized Complexity of Synthesizing Boolean Petri Nets With Restricted Dependency
论文作者
论文摘要
用培养皿网对现实世界进行建模，可以从其并行性，同步和冲突的通用概念中受益，并获得简洁而表达的系统表示。 从连续规范中合成网络的算法使得petri网的发达理论可以通过净模型应用于系统分析。 $τ$ - 类型的问题在于确定给定的标记图$ a $是否对$τ$的布尔Petri net $ n $的可及性图是同构。 如果做出积极的决定，则应构建$ n $。对于许多布尔类型的网络，该问题是NP完整的。 本文涉及$τ$ - 联合的特殊变体，该变体对目标净$ n $施加了限制：我们调查了依赖性$ d $ d $限制的tau合成（dr $τ$ s），其中$ n $的每个地方都会影响并受到大多数d过渡的影响。对于类型的$τ$，如果tau合成是np complete，则dr $τ$ s也是np complete。在本文中，我们显示由$ d $参数化的Dr $τ$ S在XP中。此外，我们证明它是W [2] -HARD，对于许多允许无条件相互作用的布尔类型设置和重置。
Modeling of real-world systems with Petri nets allows to benefit from their generic concepts of parallelism, synchronisation and conflict, and obtain a concise yet expressive system representation. Algorithms for synthesis of a net from a sequential specification enable the well-developed theory of Petri nets to be applied for the system analysis through a net model. The problem of $τ$-synthesis consists in deciding whether a given directed labeled graph $A$ is isomorphic to the reachability graph of a Boolean Petri net $N$ of type $τ$. In case of a positive decision, $N$ should be constructed. For many Boolean types of nets, the problem is NP-complete. This paper deals with a special variant of $τ$-synthesis that imposes restrictions for the target net $N$: we investigate dependency $d$-restricted tau-synthesis (DR$τ$S) where each place of $N$ can influence and be influenced by at most d transitions. For a type $τ$, if tau-synthesis is NP-complete then DR$τ$S is also NP-complete. In this paper, we show that DR$τ$S parameterized by $d$ is in XP. Furthermore, we prove that it is W[2]-hard, for many Boolean types that allow unconditional interactions set and reset.
