The complexity of synthesizing \textsf{nop}-equipped Boolean Petri nets from \(g\)-bounded inputs

DOI10.1007/978-3-662-63079-2_5zbMath1464.68264arXiv1911.05834OpenAlexW3130545160MaRDI QIDQ2032841

Ronny Tredup

Publication date: 14 June 2021

Full work available at URL: https://arxiv.org/abs/1911.05834

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (7)

Synthesis of Pure and Impure Petri Nets with Restricted Place-environments: Complexity Issues ⋮ Synthesis of inhibitor-reset Petri nets: algorithmic and complexity issues ⋮ On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets ⋮ Unnamed Item ⋮ On the parameterized complexity of the synthesis of Boolean nets with restricted place environments ⋮ The Complexity of Synthesis of b-Bounded Petri Nets ⋮ Synthesis of Petri nets with restricted place-environments: classical and parameterized

Cites Work

• Unnamed Item
• Unnamed Item
• Petri net synthesis
• The synthesis problem for elementary net systems is NP-complete
• Contextual nets
• Trace nets and process automata
• Elementary net synthesis remains NP-complete even for extremely simple inputs
• The complexity of synthesis for 43 Boolean Petri net types
• Step semantics of Boolean nets
• Flip-flop nets
• Hard tiling problems with simple tiles
• Hardness Results for the Synthesis of b-bounded Petri Nets

This page was built for publication: The complexity of synthesizing \textsf{nop}-equipped Boolean Petri nets from \(g\)-bounded inputs