Raymond Devillers ; Ronny Tredup - Synthesis of Pure and Impure Petri nets With Restricted Place-environments: Complexity Issues

fi:8814 - Fundamenta Informaticae, October 21, 2022, Volume 187, Issues 2-4: Petri Nets 2021
Synthesis of Pure and Impure Petri nets With Restricted Place-environments: Complexity IssuesArticle

Authors: Raymond Devillers ; Ronny Tredup

    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.


    Volume: Volume 187, Issues 2-4: Petri Nets 2021
    Published on: October 21, 2022
    Accepted on: July 4, 2022
    Submitted on: December 8, 2021
    Keywords: Computer Science - Formal Languages and Automata Theory

    Consultation statistics

    This page has been seen 89 times.
    This article's PDF has been downloaded 53 times.