Complexity of some problems in Petri nets

From MaRDI portal
Publication:1238999

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




Related Items (48)

Yeast: A case study for a practical use of formal methodsBounded self-stabilizing Petri netsAn \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systemsWeak Time Petri Nets Strike Back!Deadlocks and traps in Petri nets as Horn-satisfiability solutions and some related polynomially solvable problemsDeciding a class of path formulas for conflict-free Petri netsCompleteness results for conflict-free vector replacement systemsWaiting netsProblems concerning fairness and temporal logic for conflict-free Petri netsDiscrete Parameters in Petri NetsReachability problems and abstract state spaces for time Petri nets with stopwatchesOn projective and separable propertiesA survey of timed automata for the development of real-time systemsPSPACE-Completeness of the Soundness Problem of Safe Asymmetric-Choice Workflow NetsStructural Liveness of Immediate Observation Petri NetsMacro liveness graph and liveness of \(\omega\)-independent unbounded netsLinear time analysis of properties of conflict-free and general Petri netsVerifying chemical reaction network implementations: a bisimulation approachWaiting Nets: State Classes and TaxonomyBounded memory Dolev-Yao adversaries in collaborative systemsComparing the Expressiveness of Timed Automata and Timed Extensions of Petri NetsThe complexity of problems involving structurally bounded and conservative Petri netsDirected reachability for infinite-state systemsComplexity results for 1-safe netsStructure theory of equal conflict systemsVerification of Immediate Observation Population ProtocolsFinding a Witness Path for Non-liveness in Free-Choice NetsA polynomial-time algorithm to decide liveness of bounded free choice netsParameterized model checking of networks of timed automata with Boolean guardsA Framework for Classical Petri Net Problems: Conservative Petri Nets as an ApplicationVerifying polymer reaction networks using bisimulationNormal and sinkless Petri netsCollaborative planning with confidentialitySome observations on supervisory policies that enforce liveness in partially controlled free-choice Petri netsA parametric analysis of the state-explosion problem in model checkingSymbolic Reachability Analysis of Integer Timed Petri NetsA lightweight deadlock analysis for programs with threads and reentrant locksComplexity of the deadlock problem for Petri nets modeling resource allocation systemsComplexity of some problems in Petri netsCombining free choice and time in Petri netsDecidable Classes of Unbounded Petri Nets with Time and UrgencyA multiparameter analysis of the boundedness problem for vector addition systemsTime-based expressivity of time Petri nets for system specificationState space axioms for T-systemsGlobal and local views of state fairnessA polynomial time algorithm to decide pairwise concurrency of transitions for 1-bounded conflict-free Petri netsProgram schemes, arrays, Lindström quantifiers and zero-one lawsAbstraction-based incremental inductive coverability for Petri nets



Cites Work


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