scientific article; zbMATH DE number 7378560

DOI10.4230/LIPIcs.CONCUR.2018.16MaRDI QIDQ5009430

Ronny Tredup, Christian Rosenke

Publication date: 4 August 2021

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

NP-completenessparameterized complexityelementary net systemsPetri net synthesis

Mathematics Subject Classification ID

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

Related Items (8)

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 ⋮ Parameterized Complexity of Synthesizing b-Bounded (m, n)-T-Systems ⋮ On the parameterized complexity of the synthesis of Boolean nets with restricted place environments ⋮ The complexity of synthesizing \textsf{nop}-equipped Boolean Petri nets from \(g\)-bounded inputs ⋮ The complexity of synthesizing elementary net systems relative to natural parameters ⋮ The Complexity of Synthesis of b-Bounded Petri Nets

Cites Work

• Petri net synthesis
• Some complexity results on transition systems and elementary net systems
• The synthesis problem for elementary net systems is NP-complete
• Elementary net synthesis remains NP-complete even for extremely simple inputs
• The complexity of synthesizing elementary net systems relative to natural parameters
• Flip-flop nets
• Hard tiling problems with simple tiles
• Unnamed Item

This page was built for publication: