The complexity of problems involving structurally bounded and conservative Petri nets

DOI10.1016/0020-0190(91)90004-2zbMath0741.68056OpenAlexW2002058814MaRDI QIDQ1183417

Rodney R. Howell

Publication date: 28 June 1992

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(91)90004-2

zbMATH Keywords

upper boundPetri netsconcurrency

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (1)

Bounded self-stabilizing Petri nets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completeness results for single-path Petri nets
• A new polynomial-time algorithm for linear programming
• Normal Petri nets
• Petri nets and large finite sets
• Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
• An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems
• Completeness results for conflict-free vector replacement systems
• The decidability of persistence for vector addition systems
• Persistence of vector replacement systems is decidable
• The equality problem for vector addition systems is undecidable
• Complexity of some problems in Petri nets
• The covering and boundedness problems for vector addition systems
• On the finite containment problem for Petri nets
• A multiparameter analysis of the boundedness problem for vector addition systems
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Relationships between nondeterministic and deterministic tape complexities
• Parallel program schemata
• An Algorithm for the General Petri Net Reachability Problem
• The Complexity of the Finite Containment Problem for Petri Nets
• Structural properties of petri nets
• Properties of Conflict-Free and Persistent Petri Nets

This page was built for publication: The complexity of problems involving structurally bounded and conservative Petri nets