The synthesis problem for elementary net systems is NP-complete

DOI10.1016/S0304-3975(96)00219-8MaRDI QIDQ1389765zbMATH OpenFDO

Authors Eric Badouel, Luca Bernardinello, Philippe Darondeau

Publication date 30 June 1998

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(96)00219-8

zbMATH Keywords

Petri netsynthesis problem

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Elementary net synthesis remains NP-complete even for extremely simple inputs
• The synthesis problem of Petri nets
• scientific article; zbMATH DE number 512821
• Polynomial algorithms for the synthesis of bounded nets
• Flip-flop nets

Cites work

• A Symbolic Algorithm for the Synthesis of Bounded Petri Nets
• Flip-flop nets
• scientific article; zbMATH DE number 3783030 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 554482 (Why is no real title available?)
• Partial (set) 2-structures. II: State spaces of concurrent systems
• PETRI NETS AND STEP TRANSITION SYSTEMS
• Polynomial algorithms for the synthesis of bounded nets
• Some complexity results on transition systems and elementary net systems
• The synthesis problem of Petri nets

Cited in

(35)

• Bounded choice-free Petri net synthesis: algorithmic issues
• Efficient synthesis of weighted marked graphs with circular reachability graph, and beyond
• The complexity of synthesizing \textsf{nop}-equipped Boolean Petri nets from \(g\)-bounded inputs
• Synthesising elementary net systems with localities
• Topics in region theory and synthesis problems
• Edge, event and state removal: the complexity of some basic techniques that make transition systems Petri net implementable
• Synthesis of (choice-free) reset nets
• 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
• Synthesis and reengineering of persistent systems
• Elementary net synthesis remains NP-complete even for extremely simple inputs
• The complexity of synthesizing elementary net systems relative to natural parameters
• Step semantics of Boolean nets
• Real time identification of discrete event systems using Petri nets
• The power of prime cycles
• Parameterized complexity of synthesizing \(b\)-bounded \((m,n)\)-T-systems
• Discovery, Verification and Conformance of Workflows with Cancellation
• scientific article; zbMATH DE number 512821 (Why is no real title available?)
• Flip-flop nets
• Target-oriented Petri net synthesis
• Narrowing down the hardness barrier of synthesizing elementary net systems
• On the parameterized complexity of synthesizing Boolean Petri nets with restricted dependency
• Articulations and Products of Transition Systems and their Applications to Petri Net Synthesis
• The Complexity of Synthesis of b-Bounded Petri Nets
• Synthesis of Pure and Impure Petri Nets with Restricted Place-environments: Complexity Issues
• Stratified petri nets
• \(k\)-bounded Petri net synthesis from modal transition systems
• Lectures on Concurrency and Petri Nets
• On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets
• Articulation of Transition Systems and Its Application to Petri Net Synthesis
• 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
• Regions of Petri nets with a/sync connections
• Applying regions

This page was built for publication: The synthesis problem for elementary net systems is NP-complete

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