Polynomial algorithms for the synthesis of bounded nets

DOI10.1007/3-540-59293-8_207zbMATH Open1496.68212OpenAlexW1833736042MaRDI QIDQ5096743FDOQ5096743

Authors: Luca Bernardinello, Eric Badouel, Philippe Darondeau 

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

Recommendations

• Publication:4203989
• Polynomial algorithms to finite Veber problem for a tree network
• Algorithms for synthesis of polynomials implementing weakly specified Boolean functions and systems
• Polynomial algorithms for solving the quadratic bottleneck assignment problem on networks
• Polynomial dual network simplex algorithms
• Boolean algebra of nets, their synthesis and analysis
• A polynomial algorithm for computing elementary siphons in a class of Petri nets
• Polygraphic programs and polynomial-time functions
• Polynomial algorithms for solving the quadratic assignment problem on networks
• scientific article; zbMATH DE number 5925034

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)

Cites Work

• Title not available (Why is that?)
• A trace semantics for Petri Nets
• Title not available (Why is that?)
• Partial (set) 2-structures. I: Basic notions and the representation problems
• Title not available (Why is that?)
• Some complexity results on transition systems and elementary net systems
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (31)

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

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

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