论文标题
关于与依赖性有限的合成布尔培养皿网的参数化复杂性（技术报告）
On the Parameterized Complexity of Synthesizing Boolean Petri Nets With Restricted Dependency (Technical Report)
论文作者
论文摘要
$τ$ - 类型的问题在于确定给定的标记图$ a $是否对$τ$的布尔Petri net $ n $的可及性图是同构。如果做出积极的决定，则应构建$ n $。对于许多布尔类型的网络，该问题是NP完整的。本文涉及$τ$ - 联合的特殊变体，该变体对目标净$ n $施加了限制：我们调查了\ emph {依赖关系$ d $限制的$τ$ -Synsiss（Dr $τ$ s）}，其中$ n $的每个位置都会影响并受到最多$ D $ d $ d $的影响。对于类型的$τ$，如果$τ$ - 联合是np complete，则dr $τ$ s也是np complete。在本文中，我们显示由$ d $参数化的Dr $τ$ S在XP中。此外，我们证明这是$ w [2] $ - 对于许多允许无条件互动$ set $ set $和$ repoet $的布尔类型的$ W [2] $。
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 \emph{dependency $d$-restricted $τ$-synthesis (DR$τ$S)} where each place of $N$ can influence and be influenced by at most $d$ transitions. For a type $τ$, if $τ$-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$.
