On the parameterized complexity of synthesizing Boolean Petri nets with restricted dependency

MaRDI QIDQ5019696zbMATH OpenFDO

Authors Ronny Tredup, Evgeny Erofeev

Publication date 10 January 2022

Full work available at URL https://arxiv.org/abs/2009.08871, http://eptcs.web.cse.unsw.edu.au/paper.cgi?ICE2020.7

Mathematics Subject Classification ID

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

Recommendations

• 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
• The complexity of synthesizing \textsf{nop}-equipped Boolean Petri nets from \(g\)-bounded inputs
• Synthesis of structurally restricted \(b\)-bounded Petri nets: complexity results
• The Complexity of Synthesis of b-Bounded Petri Nets

Cites work

• A survey of Petri net methods for controlled discrete event systems
• Analysis and synthesis of weighted marked graph Petri nets: exact and approximate methods
• Bounded choice-free Petri net synthesis: algorithmic issues
• Bounded Petri net synthesis from modal transition systems is undecidable
• Distributing finite automata through Petri net synthesis
• Elementary net synthesis remains NP-complete even for extremely simple inputs
• Finding optimum branchings
• Flip-flop nets
• Hardness Results for the Synthesis of b-bounded Petri Nets
• scientific article; zbMATH DE number 4031000 (Why is no real title available?)
• scientific article; zbMATH DE number 52953 (Why is no real title available?)
• scientific article; zbMATH DE number 559221 (Why is no real title available?)
• Narrowing down the hardness barrier of synthesizing elementary net systems
• Parameterized algorithms
• Petri net synthesis
• Presynthesis of bounded choice-free or fork-attribution nets
• Process mining. Discovery, conformance and enhancement of business processes.
• Relabelling LTS for Petri net synthesis via solving separation problems
• Synthesis of structurally restricted \(b\)-bounded Petri nets: complexity results
• The complexity of Boolean state separation
• The complexity of synthesizing \textsf{nop}-equipped Boolean Petri nets from \(g\)-bounded inputs
• The synthesis problem for elementary net systems is NP-complete
• Theory and applications of models of computation. 16th international conference, TAMC 2020, Changsha, China, October 18--20, 2020. Proceedings
• Trace nets and process automata
• Transition systems of Elementary Net Systems with inhibitor arcs

Cited in

(8)

• The complexity of synthesizing \textsf{nop}-equipped Boolean Petri nets from \(g\)-bounded inputs
• Synthesis of Petri nets with restricted place-environments: classical and parameterized
• On the parameterized complexity of the synthesis of Boolean nets with restricted place environments
• The complexity of synthesis for 43 Boolean Petri net types
• Parameterized complexity of synthesizing \(b\)-bounded \((m,n)\)-T-systems
• The Complexity of Synthesis of b-Bounded Petri Nets
• Synthesis of Pure and Impure Petri Nets with Restricted Place-environments: Complexity Issues
• On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets

Describes a project that uses

Uses Software

• APT

This page was built for publication: On the parameterized complexity of synthesizing Boolean Petri nets with restricted dependency

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