The complexity of synthesizing elementary net systems relative to natural parameters

摘要

Elementary net systems (ENS) are the most fundamental class of Petri nets. Given a labeled transition system (TS) A, feasibility is the NP-complete decision problem whether A can be synthesized into an ENS. We analyze the impact of state degree, the number of allowed successors and predecessors of states in A, and event manifoldness, the amount of occurrences that an event can have in A, on the computational complexity of feasibility and the related event state separation property (ESSP) and state separation property (SSP). Feasibility, ESSP and SSP are NP-complete for TSs with state degree one and event manifoldness not less than three and for TSs with state degree and event manifoldness at least two. As we also show that SSP becomes tractable for TSs with state degree one and event manifoldness two, the only cases left open are ESSP and feasibility for the same input restriction.