The synthesis problem for elementary net systems is NP-complete

DOI10.1016/S0304-3975(96)00219-8zbMath0893.68111MaRDI QIDQ1389765

Eric Badouel, Philippe Darondeau, Luca Bernardinello

Publication date: 30 June 1998

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

zbMATH Keywords

Petri netsynthesis problem

Mathematics Subject Classification ID

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

Related Items (28)

Synthesis of Pure and Impure Petri Nets with Restricted Place-environments: Complexity Issues ⋮ Step semantics of Boolean 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 ⋮ Unnamed Item ⋮ Real time identification of discrete event systems using Petri nets ⋮ Unnamed Item ⋮ Discovery, Verification and Conformance of Workflows with Cancellation ⋮ Parameterized Complexity of Synthesizing b-Bounded (m, n)-T-Systems ⋮ On the parameterized complexity of the synthesis of Boolean nets with restricted place environments ⋮ Synthesis and reengineering of persistent systems ⋮ Regions of Petri nets with a/sync connections ⋮ 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 ⋮ Applying regions ⋮ The complexity of synthesizing elementary net systems relative to natural parameters ⋮ The Power of Prime Cycles ⋮ Target-oriented Petri Net Synthesis ⋮ Synthesising elementary net systems with localities ⋮ k-Bounded Petri Net Synthesis from Modal Transition Systems. ⋮ Articulations and Products of Transition Systems and their Applications to Petri Net Synthesis ⋮ The Complexity of Synthesis of b-Bounded Petri Nets ⋮ Topics in region theory and synthesis problems ⋮ Synthesis of (choice-free) reset nets ⋮ Synthesis of Petri nets with restricted place-environments: classical and parameterized

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Partial (set) 2-structures. II: State spaces of concurrent systems
• Some complexity results on transition systems and elementary net systems
• The synthesis problem of Petri nets
• A Symbolic Algorithm for the Synthesis of Bounded Petri Nets
• PETRI NETS AND STEP TRANSITION SYSTEMS
• Flip-flop nets
• Polynomial algorithms for the synthesis of bounded nets

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