Complexity results for 1-safe nets
From MaRDI portal
Publication:672459
DOI10.1016/0304-3975(94)00231-7zbMath0873.68146OpenAlexW1996760951MaRDI QIDQ672459
Allan Cheng, Jens Palsberg, Javier Esparza
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(94)00231-7
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 (32)
Waiting nets ⋮ On the Complexity of Reconfiguration in Systems with Legacy Components ⋮ Petri nets, traces, and local model checking ⋮ PSPACE-Completeness of the Soundness Problem of Safe Asymmetric-Choice Workflow Nets ⋮ Linear time analysis of properties of conflict-free and general Petri nets ⋮ Nested-unit Petri nets ⋮ Generalized Alignment-Based Trace Clustering of Process Behavior ⋮ Parameterized Analysis of Immediate Observation Petri Nets ⋮ Concurrency in Boolean networks ⋮ A P systems variant for reasoning about sequential controllability of Boolean networks ⋮ Waiting Nets: State Classes and Taxonomy ⋮ Static analysis and stochastic search for reachability problem ⋮ Verification of Immediate Observation Population Protocols ⋮ A process algebraic view of shared dataspace coordination ⋮ Partially commutative inverse monoids. ⋮ The complexity of verifying population protocols ⋮ Complexity of the deadlock problem for Petri nets modeling resource allocation systems ⋮ Deciding the liveness for a subclass of weighted Petri nets based on structurally circular wait ⋮ Robustness in Interaction Systems ⋮ Sequential reprogramming of biological network fate ⋮ Context-Bounded Analysis of Concurrent Queue Systems ⋮ Distributed semantics for the \(\pi \)-calculus based on Petri nets with inhibitor ARCS ⋮ Unnamed Item ⋮ Anti-alignments in Conformance Checking – The Dark Side of Process Models ⋮ Analyzing Reachability for Some Petri Nets With Fast Growing Markings ⋮ Comparative analysis of the expressiveness of shared dataspace coordination ⋮ On Petri Nets with Hierarchical Special Arcs ⋮ On the expressiveness of Linda coordination primitives. ⋮ Analysis issues in Petri nets with inhibitor arcs ⋮ Analysis of safeness in a Petri net-based specification of the control part of cyber-physical systems ⋮ Timed Petri nets with reset for pipelined synchronous circuit design ⋮ Efficient algorithms for three reachability problems in safe 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
- Unnamed Item
- Unnamed Item
- Partial order behaviour and structure of Petri nets
- Completeness results for conflict-free vector replacement systems
- Problems concerning fairness and temporal logic for conflict-free Petri nets
- A polynomial-time algorithm to decide liveness of bounded free choice nets
- The equality problem for vector addition systems is undecidable
- Complexity of some problems in Petri nets
- Model checking using net unfoldings
- Marked directed graphs
- Synchronisationsgraphen
- An Algorithm for the General Petri Net Reachability Problem
- Properties of Conflict-Free and Persistent Petri Nets
- Deciding true concurrency equivalences on finite safe nets (preliminary report)
- Advances in Petri nets 1992
This page was built for publication: Complexity results for 1-safe nets
