Linear time analysis of properties of conflict-free and general Petri nets
From MaRDI portal
Publication:620942
DOI10.1016/j.tcs.2010.09.030zbMath1206.68206MaRDI QIDQ620942
Paola Alimonti, Umberto Nanni, Esteban Feuerstein, Luigi Laura
Publication date: 2 February 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.09.030
boundedness; liveness; Petri nets; directed hypergraphs; marked graphs; incremental algorithms; conflict-free Petri nets; coverability
68R10: Graph theory (including graph drawing) in computer science
68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Related Items
Directed hypergraphs: introduction and fundamental algorithms -- a survey, Reachability analysis of low-order discrete state reaction networks obeying conservation laws, Static analysis of Biological Regulatory Networks dynamics using abstract interpretation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity results for 1-safe nets
- A taxonomy of fairness and temporal logic problems for Petri nets
- Dynamic maintenance of directed hypergraphs
- Linear connectivity problems in directed hypergraphs
- An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems
- Problems concerning fairness and temporal logic for conflict-free Petri nets
- A unified approach for deciding the existence of certain petri net paths
- A polynomial-time algorithm to decide liveness of bounded free choice nets
- A decidability theorem for a class of vector-addition systems
- Complexity of some problems in Petri nets
- Directed recursive labelnode hypergraphs: A new representation-language
- The covering and boundedness problems for vector addition systems
- Partially dynamic maintenance of minimum weight hyperpaths
- Directed hypergraphs and applications
- Parallel program schemata
- On the computational power of pushdown automata
- Marked directed graphs
- Graph Algorithms for Functional Dependency Manipulation
- A Note on Persistent Petri Nets
- A fully dynamic reachability algorithm for directed graphs with an almost linear update time
- An Algorithm for the General Petri Net Reachability Problem
- On-line algorithms for polynomially solvable satisfiability problems
- Efficiency of a Good But Not Linear Set Union Algorithm
- Properties of Conflict-Free and Persistent Petri Nets