Ronny Tredup - The Complexity of Synthesis of $b$-Bounded Petri Nets

fi:8467 - Fundamenta Informaticae, December 23, 2021, Volume 183, Issues 1-2: Petri Nets 2019
The Complexity of Synthesis of $b$-Bounded Petri NetsArticle

Authors: Ronny Tredup

    For a fixed type of Petri nets $\tau$, \textsc{$\tau$-Synthesis} is the task of finding for a given transition system $A$ a Petri net $N$ of type $\tau$ ($\tau$-net, for short) whose reachability graph is isomorphic to $A$ if there is one. The decision version of this search problem is called \textsc{$\tau$-Solvability}. If an input $A$ allows a positive decision, then it is called $\tau$-solvable and a sought net $N$ $\tau$-solves $A$. As a well known fact, $A$ is $\tau$-solvable if and only if it has the so-called $\tau$-\emph{event state separation property} ($\tau$-ESSP, for short) and the $\tau$-\emph{state separation property} ($\tau$-SSP, for short). The question whether $A$ has the $\tau$-ESSP or the $\tau$-SSP defines also decision problems. In this paper, for all $b\in \mathbb{N}$, we completely characterize the computational complexity of \textsc{$\tau$-Solvability}, \textsc{$\tau$-ESSP} and \textsc{$\tau$-SSP} for the types of pure $b$-bounded Place/Transition-nets, the $b$-bounded Place/Transition-nets and their corresponding $\mathbb{Z}_{b+1}$-extensions.


    Volume: Volume 183, Issues 1-2: Petri Nets 2019
    Published on: December 23, 2021
    Accepted on: September 22, 2021
    Submitted on: September 10, 2021
    Keywords: Computer Science - Computational Complexity

    Consultation statistics

    This page has been seen 163 times.
    This article's PDF has been downloaded 90 times.