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_13zbMATH Open1489.68168OpenAlexW3172765973MaRDI QIDQ2117174FDOQ2117174

Authors: Ronny Tredup 

Publication date: 21 March 2022

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

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

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)

Cites Work

• Process mining. Discovery, conformance and enhancement of business processes.
• Logic Synthesis for Asynchronous Controllers and Interfaces
• Synthesis and reengineering of persistent systems
• Petri net synthesis
• Polynomial algorithms for the synthesis of bounded nets
• Distributing finite automata through Petri net synthesis
• Petri net distributability
• The label splitting problem
• Relabelling LTS for Petri net synthesis via solving separation problems

Cited In (2)

• On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets
• Some Basic Techniques Allowing Petri Net Synthesis: Complexity and Algorithmic Issues

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)