Edge, event and state removal: the complexity of some basic techniques that make transition systems Petri net implementable

DOI10.1007/978-3-030-76983-3_13MaRDI QIDQ2117174zbMATH OpenOpenAlexFDO

Authors Ronny Tredup

Publication date 21 March 2022

Full work available at URL https://doi.org/10.1007/978-3-030-76983-3_13

Mathematics Subject Classification ID

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

Recommendations

• Simultaneous Petri Net Synthesis
• Elementary net synthesis remains NP-complete even for extremely simple inputs
• The synthesis problem for elementary net systems is NP-complete
• The complexity of synthesizing elementary net systems relative to natural parameters
• Synthesis of structurally restricted \(b\)-bounded Petri nets: complexity results

Cites work

• Distributing finite automata through Petri net synthesis
• Logic Synthesis for Asynchronous Controllers and Interfaces
• Petri net distributability
• 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
• Synthesis and reengineering of persistent systems
• The label splitting problem

Cited in

(2)

• Some Basic Techniques Allowing Petri Net Synthesis: Complexity and Algorithmic 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: Edge, event and state removal: the complexity of some basic techniques that make transition systems Petri net implementable

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