The synthesis problem for elementary net systems is NP-complete

DOI10.1016/S0304-3975(96)00219-8zbMATH Open0893.68111MaRDI QIDQ1389765FDOQ1389765

Authors: Eric Badouel, Luca Bernardinello, Philippe Darondeau 

Publication date: 30 June 1998

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

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

zbMATH Keywords

Petri netsynthesis problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (34)

• Flip-flop nets
• Synthesis of (choice-free) reset nets
• The Complexity of Synthesis of b-Bounded Petri Nets
• Fixed Parameter Tractability and Polynomial Time Results for the Synthesis of b-bounded Petri Nets
• Parameterized complexity of synthesizing \(b\)-bounded \((m,n)\)-T-systems
• Target-oriented Petri net synthesis
• Edge, event and state removal: the complexity of some basic techniques that make transition systems Petri net implementable
• Topics in region theory and synthesis problems
• Synthesis of inhibitor-reset Petri nets: algorithmic and complexity issues
• Hardness Results for the Synthesis of b-bounded Petri Nets
• Regions of Petri nets with a/sync connections
• Synthesis and reengineering of persistent systems
• Applying regions
• The power of prime cycles
• \(k\)-bounded Petri net synthesis from modal transition systems
• Narrowing down the hardness barrier of synthesizing elementary net systems
• On the parameterized complexity of synthesizing Boolean Petri nets with restricted dependency
• 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
• Bounded choice-free Petri net synthesis: algorithmic issues
• On the parameterized complexity of the synthesis of Boolean nets with restricted place environments
• Elementary net synthesis remains NP-complete even for extremely simple inputs
• Synthesis of Petri nets with restricted place-environments: classical and parameterized
• Real time identification of discrete event systems using 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
• Discovery, Verification and Conformance of Workflows with Cancellation
• Stratified petri nets
• Synthesising elementary net systems with localities
• Step semantics of Boolean nets
• Articulations and Products of Transition Systems and their Applications to Petri Net Synthesis
• Lectures on Concurrency and Petri Nets
• The complexity of synthesizing elementary net systems relative to natural parameters
• Synthesis of Pure and Impure Petri Nets with Restricted Place-environments: Complexity Issues

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)