Parameterized complexity of synthesizing b-bounded (m,n)-T-systems

DOI10.1007/978-3-030-38919-2_19MaRDI QIDQ3297771zbMATH OpenOpenAlexFDO

Authors Ronny Tredup

Publication date 20 July 2020

Published in SOFSEM 2020: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-38919-2_19

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Synthesis of structurally restricted \(b\)-bounded Petri nets: complexity results
• The Complexity of Synthesis of b-Bounded Petri Nets
• Synthesis of Petri nets with restricted place-environments: classical and parameterized
• On the parameterized complexity of synthesizing Boolean Petri nets with restricted dependency
• On the parameterized complexity of the synthesis of Boolean nets with restricted place environments

Cites work

• Analysis and synthesis of weighted marked graph Petri nets
• Bounded Petri net synthesis from modal transition systems is undecidable
• Characterisation of the state spaces of live and bounded marked graph Petri nets
• Elementary net synthesis remains NP-complete even for extremely simple inputs
• Lectures on Concurrency and Petri Nets
• Narrowing down the hardness barrier of synthesizing elementary net systems
• Parameterized algorithms
• Petri net synthesis
• Polynomial algorithms for the synthesis of bounded nets
• State space axioms for T-systems
• Synthesis of bounded choice-free Petri nets
• Synthesis of structurally restricted \(b\)-bounded Petri nets: complexity results
• The synthesis of Petri nets from path-automatic specifications
• The synthesis problem for elementary net systems is NP-complete
• \(k\)-bounded Petri net synthesis from modal transition systems

Cited in

(4)

• Fixed Parameter Tractability and Polynomial Time Results for the Synthesis of b-bounded Petri Nets
• On the parameterized complexity of the synthesis of Boolean nets with restricted place environments
• Synthesis of Petri nets with restricted place-environments: classical and parameterized
• Synthesis of structurally restricted \(b\)-bounded Petri nets: complexity results

Describes a project that uses

Uses Software

• APT

This page was built for publication: Parameterized complexity of synthesizing \(b\)-bounded \((m,n)\)-T-systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3297771)