Co-Finiteness and Co-Emptiness of Reachability Sets in Vector Addition Systems with States
2019
The coverability and boundedness problems are well-known exponential-space complete problems for vector addition systems with states (or Petri nets). The boundedness problem asks if the reachability set (for a given initial configuration) is finite. Here we consider a dual problem, the co-finiteness problem that asks if the complement of the reachability set is finite; by restricting the question we get the co-emptiness (or universality) problem that asks if all configurations are reachable.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI