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

DOI10.1007/978-3-319-91268-4_3MaRDI QIDQ2280178zbMATH OpenOpenAlexFDO

Authors Ronny Tredup, Christian Rosenke, Karsten Wolf

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

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

Recommendations

• The synthesis problem for elementary net systems is NP-complete
• Narrowing down the hardness barrier of synthesizing elementary net systems
• The complexity of synthesizing elementary net systems relative to natural parameters
• Some complexity results on transition systems and elementary net systems
• Reachability is NP-complete even for the simplest neural networks
• On the parameterized complexity of \(d\)-restricted Boolean net synthesis
• Polynomial algorithms for the synthesis of bounded nets
• Cyclomatic complexity for generalized nets
• On the Complexity of Negation-Limited Boolean Networks
• On the complexity of negation-limited Boolean networks (preliminary version)

Cited in

(11)

• The synthesis problem for elementary net systems is NP-complete
• The complexity of synthesizing \textsf{nop}-equipped Boolean Petri nets from \(g\)-bounded inputs
• Edge, event and state removal: the complexity of some basic techniques that make transition systems Petri net implementable
• On the parameterized complexity of the synthesis of Boolean nets with restricted place environments
• The complexity of synthesizing elementary net systems relative to natural parameters
• Parameterized complexity of synthesizing \(b\)-bounded \((m,n)\)-T-systems
• Narrowing down the hardness barrier of synthesizing elementary net systems
• On the parameterized complexity of synthesizing Boolean Petri nets with restricted dependency
• The Complexity of Synthesis of b-Bounded Petri Nets
• 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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2280178)