Polynomial algorithms for the synthesis of bounded nets

DOI10.1007/3-540-59293-8_207zbMath1496.68212OpenAlexW1833736042MaRDI QIDQ5096743

Luca Bernardinello, Philippe Darondeau, Eric Badouel

Publication date: 18 August 2022

Published in: TAPSOFT '95: Theory and Practice of Software Development (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-59293-8_207

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (24)

Synthesis of Pure and Impure Petri Nets with Restricted Place-environments: Complexity Issues ⋮ Some Basic Techniques Allowing Petri Net Synthesis: Complexity and Algorithmic Issues ⋮ Discovering workflow nets using integer linear programming ⋮ Synthesis of inhibitor-reset Petri nets: algorithmic and complexity issues ⋮ The synthesis problem for elementary net systems is NP-complete ⋮ On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets ⋮ Articulation of Transition Systems and Its Application to Petri Net Synthesis ⋮ Hardness Results for the Synthesis of b-bounded Petri Nets ⋮ Fixed Parameter Tractability and Polynomial Time Results for the Synthesis of b-bounded Petri Nets ⋮ A Symbolic Algorithm for the Synthesis of Bounded Petri Nets ⋮ Process Discovery Using Integer Linear Programming ⋮ Parameterized Complexity of Synthesizing b-Bounded (m, n)-T-Systems ⋮ Synthesis and reengineering of persistent systems ⋮ Bounded choice-free Petri net synthesis: algorithmic issues ⋮ Efficient synthesis of weighted marked graphs with circular reachability graph, and beyond ⋮ Synthesis of Nets with Step Firing Policies ⋮ Target-oriented Petri Net Synthesis ⋮ Equality of languages coincides with isomorphism of reachable state graphs for bounded and persistent Petri nets ⋮ Articulations and Products of Transition Systems and their Applications to Petri Net Synthesis ⋮ The Complexity of Synthesis of b-Bounded Petri Nets ⋮ Analysis of safeness in a Petri net-based specification of the control part of cyber-physical systems ⋮ Topics in region theory and synthesis problems ⋮ Edge, event and state removal: the complexity of some basic techniques that make transition systems Petri net implementable ⋮ Synthesis of Petri nets with restricted place-environments: classical and parameterized

Cites Work

• Partial (set) 2-structures. I: Basic notions and the representation problems
• Some complexity results on transition systems and elementary net systems
• A trace semantics for Petri Nets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Polynomial algorithms for the synthesis of bounded nets