The complexity of synthesizing elementary net systems relative to natural parameters

DOI10.1016/j.jcss.2019.12.007zbMath1435.68214OpenAlexW2999082282WikidataQ126356223 ScholiaQ126356223MaRDI QIDQ2304629

Christian Rosenke, Ronny Tredup

Publication date: 13 March 2020

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2019.12.007

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (2)

Unnamed Item ⋮ Topics in region theory and synthesis problems

Cites Work

• Unnamed Item
• Unnamed Item
• 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 synthesis for 43 Boolean Petri net types
• Flip-flop nets
• Hard tiling problems with simple tiles

This page was built for publication: The complexity of synthesizing elementary net systems relative to natural parameters