On the parameterized complexity of the synthesis of Boolean nets with restricted place environments

DOI10.1016/J.TCS.2021.08.014MaRDI QIDQ2235733zbMATH OpenOpenAlexFDO

Authors Ronny Tredup, Evgeny Erofeev

Publication date 21 October 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2021.08.014

zbMATH Keywords

parameterized complexityPetri netsynthesistransition system

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• On the parameterized complexity of synthesizing Boolean Petri nets with restricted dependency
• 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
• Parameterized complexity of synthesizing \(b\)-bounded \((m,n)\)-T-systems

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
• Contextual nets
• Distributing finite automata through Petri net synthesis
• Elementary net synthesis remains NP-complete even for extremely simple inputs
• Finding optimum branchings
• Flip-flop 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 1302042 (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
• Occupancy number restricted Boolean Petri net synthesis: a fixed-parameter algorithm
• On the parameterized complexity of \(d\)-restricted Boolean net synthesis
• On the parameterized complexity of synthesizing Boolean Petri nets with restricted dependency
• Parameterized algorithms
• Parametrized complexity theory.
• Petri net synthesis
• Presynthesis of bounded choice-free or fork-attribution nets
• Process mining. Discovery, conformance and enhancement of business processes.
• Synthesis of structurally restricted \(b\)-bounded Petri nets: complexity results
• The complexity of synthesizing \textsf{nop}-equipped Boolean Petri nets from \(g\)-bounded inputs
• The synthesis problem for elementary net systems is NP-complete
• Trace nets and process automata
• Transition systems of Elementary Net Systems with inhibitor arcs

Cited in

(5)

• 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
• Parameterized complexity of synthesizing \(b\)-bounded \((m,n)\)-T-systems
• On the parameterized complexity of synthesizing Boolean Petri nets with restricted dependency
• On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets

This page was built for publication: On the parameterized complexity of the synthesis of Boolean nets with restricted place environments

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