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

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