10.46298/fi-2022-8814
https://fi.episciences.org/8814
Devillers, Raymond
Raymond
Devillers
Tredup, Ronny
Ronny
Tredup
Synthesis of Pure and Impure Petri nets With Restricted Place-environments: Complexity Issues
Petri net synthesis consists in deciding for a given transition system $A$
whether there exists a Petri net $N$ whose reachability graph is isomorphic to
$A$. Several works examined the synthesis of Petri net subclasses that
restrict, for every place $p$ of the net, the cardinality of its preset or of
its postset or both in advance by small natural numbers $\varrho$ and $\kappa$,
respectively, such as for example (weighted) marked graphs, (weighted)
T-systems and choice-free nets. In this paper, we study the synthesis aiming at
Petri nets which have such restricted place environments, from the viewpoint of
classical and parameterized complexity: We first show that, for any fixed
natural numbers $\varrho$ and $\kappa$, deciding whether for a given transition
system $A$ there is a Petri net $N$ such that (1) its reachability graph is
isomorphic to $A$ and (2) for every place $p$ of $N$ the preset of $p$ has at
most $\varrho$ and the postset of $p$ has at most $\kappa$ elements is doable
in polynomial time. Secondly, we introduce a modified version of the problem,
namely Environment Restricted Synthesis (ERS, for short), where $\varrho$ and
$\kappa$ are part of the input, and show that ERS is NP-complete, regardless
whether the sought net is impure or pure. In case of the impure nets, our
methods also imply that ERS parameterized by $\varrho+\kappa$ is $W[2]$-hard.
episciences.org
Computer Science - Formal Languages and Automata Theory
Attribution 4.0 International (CC BY 4.0)
2022-07-04
2022-10-21
2022-10-21
eng
journal article
arXiv:2112.03608
10.48550/arXiv.2112.03608
1875-8681
https://fi.episciences.org/8814/pdf
VoR
application/pdf
Fundamenta Informaticae
Volume 187, Issues 2-4: Petri Nets 2021
Researchers
Students