Affiliations: Institut für Informatik, Theoretische Informatik, Universität Rostock, Albert-Einstein-Straße 22, 18059, Rostock, Germany. [email protected]
Correspondence:
[*]
Address for correspondence: Universität Rostock, Institut für Informatik, Theoretische Informatik, Albert-Einstein-Straße 22, 18059, Rostock, Germany
Abstract: For a fixed type of Petri nets τ, τ-SYNTHESIS is the task of finding for a given transition system A a Petri net N of type τ(τ-net, for short) whose reachability graph is isomorphic to A if there is one. The decision version of this search problem is called τ-SOLVABILITY. If an input A allows a positive decision, then it is called τ-solvable and a sought net N τ-solves A. As a well known fact, A is τ-solvable if and only if it has the so-called τ-event state separation property (τ-ESSP, for short) and the τ-state separation property (τ-SSP, for short). The question whether A has the τ-ESSP or the τ-SSP defines also decision problems. In this paper, for all b ∈ ℕ, we completely characterize the computational complexity of τ-SOLVABILITY, τ-ESSP and τ-SSP for the types of pure b-bounded Place/Transition-nets, the b-bounded Place/Transitionnets and their corresponding ℤb+1-extensions.
Keywords: Petri nets, synthesis, b-bounded, SSP, ESSP, solvability
