Complexity of some problems in Petri nets

DOI10.1016/0304-3975(77)90014-7zbMath0357.68048OpenAlexW2083567135MaRDI QIDQ1238999

Neil D. Jones, Y. Edmund Lien, Lawrence H. Landweber

Publication date: 1977

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://digital.library.wisc.edu/1793/57994

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (48)

Yeast: A case study for a practical use of formal methods ⋮ Bounded self-stabilizing Petri nets ⋮ An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems ⋮ Weak Time Petri Nets Strike Back! ⋮ Deadlocks and traps in Petri nets as Horn-satisfiability solutions and some related polynomially solvable problems ⋮ Deciding a class of path formulas for conflict-free Petri nets ⋮ Completeness results for conflict-free vector replacement systems ⋮ Waiting nets ⋮ Problems concerning fairness and temporal logic for conflict-free Petri nets ⋮ Discrete Parameters in Petri Nets ⋮ Reachability problems and abstract state spaces for time Petri nets with stopwatches ⋮ On projective and separable properties ⋮ A survey of timed automata for the development of real-time systems ⋮ PSPACE-Completeness of the Soundness Problem of Safe Asymmetric-Choice Workflow Nets ⋮ Structural Liveness of Immediate Observation Petri Nets ⋮ Macro liveness graph and liveness of \(\omega\)-independent unbounded nets ⋮ Linear time analysis of properties of conflict-free and general Petri nets ⋮ Verifying chemical reaction network implementations: a bisimulation approach ⋮ Waiting Nets: State Classes and Taxonomy ⋮ Bounded memory Dolev-Yao adversaries in collaborative systems ⋮ Comparing the Expressiveness of Timed Automata and Timed Extensions of Petri Nets ⋮ The complexity of problems involving structurally bounded and conservative Petri nets ⋮ Directed reachability for infinite-state systems ⋮ Complexity results for 1-safe nets ⋮ Structure theory of equal conflict systems ⋮ Verification of Immediate Observation Population Protocols ⋮ Finding a Witness Path for Non-liveness in Free-Choice Nets ⋮ A polynomial-time algorithm to decide liveness of bounded free choice nets ⋮ Parameterized model checking of networks of timed automata with Boolean guards ⋮ A Framework for Classical Petri Net Problems: Conservative Petri Nets as an Application ⋮ Verifying polymer reaction networks using bisimulation ⋮ Normal and sinkless Petri nets ⋮ Collaborative planning with confidentiality ⋮ Some observations on supervisory policies that enforce liveness in partially controlled free-choice Petri nets ⋮ A parametric analysis of the state-explosion problem in model checking ⋮ Symbolic Reachability Analysis of Integer Timed Petri Nets ⋮ A lightweight deadlock analysis for programs with threads and reentrant locks ⋮ Complexity of the deadlock problem for Petri nets modeling resource allocation systems ⋮ Complexity of some problems in Petri nets ⋮ Combining free choice and time in Petri nets ⋮ Decidable Classes of Unbounded Petri Nets with Time and Urgency ⋮ A multiparameter analysis of the boundedness problem for vector addition systems ⋮ Time-based expressivity of time Petri nets for system specification ⋮ State space axioms for T-systems ⋮ Global and local views of state fairness ⋮ A polynomial time algorithm to decide pairwise concurrency of transitions for 1-bounded conflict-free Petri nets ⋮ Program schemes, arrays, Lindström quantifiers and zero-one laws ⋮ Abstraction-based incremental inductive coverability for Petri nets

Cites Work

This page was built for publication: Complexity of some problems in Petri nets