2019/03/17 by Ronny Tredup, Tredup, Ronny
Business, Management and Accounting · Computer Science · #Business Process Modeling and Analysis #FOS: Computer and information sciences #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Petri Nets in System Modeling #Service-Oriented Architecture and Web Services
paper · pdf · doi:10.48550/arxiv.1904.01094
openalex publication_date 2019/03/17 · openalex created_date 2022/07/29 · openalex updated_date 2026/07/28
Synthesis for a type \τ of Petri nets is the following search problem:\nFor a transition system A, find a Petri net N of type \τ whose state\ngraph is isomorphic to A, if there is one. To determine the computational\ncomplexity of synthesis for types of bounded Petri nets we investigate their\ncorresponding decision version, called feasibility. We show that feasibility is\nNP-complete for (pure) b-bounded P/T-nets if b\∈ \ℕ+. We extend\n(pure) b-bounded P/T-nets by the additive group \ℤb+1 of\nintegers modulo (b+1) and show feasibility to be NP-complete for the\nresulting type. To decide if A has the event state separation property is\nshown to be NP-complete for (pure) b-bounded and group extended (pure)\nb-bounded P/T-nets. Deciding if A has the state separation property is\nproven to be NP-complete for (pure) b-bounded P/T-nets.\n