Elementary net synthesis remains NP-complete even for extremely simple inputs

DOI10.1007/978-3-319-91268-4_3zbMath1427.68211OpenAlexW2801657308MaRDI QIDQ2280178

Christian Rosenke, Ronny Tredup, Karsten Schmidt

Publication date: 18 December 2019

Full work available at URL: https://doi.org/10.1007/978-3-319-91268-4_3

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (9)

Hardness Results for the Synthesis of b-bounded Petri Nets ⋮ Fixed Parameter Tractability and Polynomial Time Results for the Synthesis of b-bounded Petri Nets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized Complexity of Synthesizing b-Bounded (m, n)-T-Systems ⋮ On the parameterized complexity of the synthesis of Boolean nets with restricted place environments ⋮ The complexity of synthesizing \textsf{nop}-equipped Boolean Petri nets from \(g\)-bounded inputs ⋮ The complexity of synthesizing elementary net systems relative to natural parameters ⋮ The Complexity of Synthesis of b-Bounded Petri Nets

This page was built for publication: Elementary net synthesis remains NP-complete even for extremely simple inputs