Hardness Results for the Synthesis of b-bounded Petri Nets

DOI10.1007/978-3-030-21571-2_9arXiv1904.01094MaRDI QIDQ6144211

Ronny Tredup

Publication date: 29 January 2024

Published in: Application and Theory of Petri Nets and Concurrency (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Unnamed Item ⋮ The complexity of synthesizing \textsf{nop}-equipped Boolean Petri nets from \(g\)-bounded inputs ⋮ Articulations and Products of Transition Systems and their Applications to Petri Net Synthesis ⋮ Synthesis of Petri nets with restricted place-environments: classical and parameterized

Cites Work

• Unnamed Item
• Unnamed Item
• Petri net synthesis
• Some complexity results on transition systems and elementary net systems
• A survey of Petri net methods for controlled discrete event systems
• The synthesis problem for elementary net systems is NP-complete
• Distributing finite automata through Petri net synthesis
• Elementary net synthesis remains NP-complete even for extremely simple inputs
• The complexity of synthesis for 43 Boolean Petri net types
• Process Mining
• Flip-flop nets
• Polynomial algorithms for the synthesis of bounded nets
• k-Bounded Petri Net Synthesis from Modal Transition Systems.
• Hard tiling problems with simple tiles

This page was built for publication: Hardness Results for the Synthesis of b-bounded Petri Nets