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

DOI10.1007/978-3-662-63079-2_5MaRDI QIDQ2032841zbMATH OpenOpenAlexFDO

Authors 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)

Abstract: Boolean Petri nets equipped with nop allow places and transitions to be independent by being related by nop. We characterize for any fixed natural number g the computational complexity of synthesizing nop-equipped Boolean Petri nets from labeled directed graphs whose states have at most g incoming and at most g outgoing arcs.

Recommendations

• On the parameterized complexity of synthesizing Boolean Petri nets with restricted dependency
• The Complexity of Synthesis of b-Bounded Petri Nets
• The complexity of synthesis for 43 Boolean Petri net types
• Synthesis of structurally restricted \(b\)-bounded Petri nets: complexity results
• On the parameterized complexity of the synthesis of Boolean nets with restricted place environments
• Bounded choice-free Petri net synthesis: algorithmic issues
• On the parameterized complexity of \(d\)-restricted Boolean net synthesis
• On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets
• Occupancy number restricted Boolean Petri net synthesis: a fixed-parameter algorithm
• Synthesis of bounded choice-free Petri nets

Cites work

• Contextual nets
• Elementary net synthesis remains NP-complete even for extremely simple inputs
• Flip-flop nets
• Hard tiling problems with simple tiles
• Hardness Results for the Synthesis of b-bounded Petri Nets
• scientific article; zbMATH DE number 1302042 (Why is no real title available?)
• Narrowing down the hardness barrier of synthesizing elementary net systems
• Petri net synthesis
• Step semantics of Boolean nets
• The complexity of synthesis for 43 Boolean Petri net types
• The synthesis problem for elementary net systems is NP-complete
• Trace nets and process automata
• Transition systems of Elementary Net Systems with inhibitor arcs

Cited in

(8)

• Synthesis of Petri nets with restricted place-environments: classical and parameterized
• Synthesis of inhibitor-reset Petri nets: algorithmic and complexity issues
• On the parameterized complexity of the synthesis of Boolean nets with restricted place environments
• The complexity of synthesis for 43 Boolean Petri net types
• On the parameterized complexity of synthesizing Boolean Petri nets with restricted dependency
• The Complexity of Synthesis of b-Bounded Petri Nets
• Synthesis of Pure and Impure Petri Nets with Restricted Place-environments: Complexity Issues
• On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets

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

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