On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets

DOI10.3233/FI-222161MaRDI QIDQ6070613zbMATH OpenFDO

Authors Raymond Devillers, Ronny Tredup

Publication date 23 November 2023

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.09233

zbMATH Keywords

Boolean typescomplexityedge-removalevent-removallabel-splittingPetri netstate-removalsynthesis

Mathematics Subject Classification ID

Computer science (68-XX)

Abstract: Synthesis consists in deciding whether a given labeled transition system (TS) $A$ can be implemented by a net $N$ of type $au$. In case of a negative decision, it may be possible to convert $A$ into an implementable TS $B$ by applying various modification techniques, like relabeling edges that previously had the same label, suppressing edges/states/events, etc. It may however be useful to limit the number of such modifications to stay close to the original problem, or optimize the technique. In this paper, we show that most of the corresponding problems are NP-complete if $au$ corresponds to the type of flip-flop nets or some flip-flop net derivatives.

Recommendations

• Some complexity results on transition systems and elementary net systems
• On the parameterized complexity of the synthesis of Boolean nets with restricted place environments
• On the Complexity of Negation-Limited Boolean Networks
• The complexity of Boolean function implementation in some classes of automaton circuits
• On the complexity of the evaluation of transient extensions of Boolean functions
• On the complexity of the evaluation of transient extensions of Boolean functions
• The complexity of synthesis for 43 Boolean Petri net types
• On the complexity of negation-limited Boolean networks (preliminary version)
• On the parameterized complexity of synthesizing Boolean Petri nets with restricted dependency
• On the parameterized complexity of \(d\)-restricted Boolean net synthesis

Cites work

• A survey of Petri net methods for controlled discrete event systems
• Contextual nets
• Deriving Petri nets from finite transition systems
• Distributing finite automata through Petri net synthesis
• Edge, event and state removal: the complexity of some basic techniques that make transition systems Petri net implementable
• Flip-flop nets
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1302042 (Why is no real title available?)
• Petri net synthesis
• Polynomial algorithms for the synthesis of bounded nets
• Process mining. Discovery, conformance and enhancement of business processes.
• Relabelling LTS for Petri net synthesis via solving separation problems
• Some Basic Techniques Allowing Petri Net Synthesis: Complexity and Algorithmic Issues
• Step semantics of Boolean nets
• The complexity of Boolean state separation
• The complexity of synthesizing \textsf{nop}-equipped Boolean Petri nets from \(g\)-bounded inputs
• The complexity of the label-splitting-problem for flip-flop-nets
• The label splitting problem
• The synthesis problem for elementary net systems is NP-complete
• Theory and applications of models of computation. 15th annual conference, TAMC 2019, Kitakyushu, Japan, April 13--16, 2019. Proceedings
• Trace nets and process automata
• Transition systems of Elementary Net Systems with inhibitor arcs

Cited in

(3)

• Some complexity results on transition systems and elementary net systems
• The complexity of synthesizing \textsf{nop}-equipped Boolean Petri nets from \(g\)-bounded inputs
• Some Basic Techniques Allowing Petri Net Synthesis: Complexity and Algorithmic Issues

This page was built for publication: On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets

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