A multiparameter analysis of the boundedness problem for vector addition systems (Q1819938)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3995066
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A multiparameter analysis of the boundedness problem for vector addition systems |
scientific article; zbMATH DE number 3995066 |
Statements
A multiparameter analysis of the boundedness problem for vector addition systems (English)
0 references
1986
0 references
The authors give a careful analysis of the complexity of the boundedness problem (BP; ''is the reachability set infinite?'') for vector addition systems (VAS) and vector addition systems with states (VASS), which are known to be equivalent to Petri nets. Upper and lower bounds for the complexity are given in dependence of three parameters: k: dimension of vectors, l: maximal bit length of vector components, n: number of states. The BP for such VASS(k,l,n) can be solved in \(O((l+\log n)*2^{c*k*\log k})\) nondeterministic space for some constant c (an improvement of Rackoff's result). Lipton's lower bound is improved to \(O((l+\log n)*2^{c*k})\). Furthermore, some complexity results for fixed small k and connections to nets of communicating finite state machines (CFSM) are given.
0 references
complexity of the boundedness problem
0 references
reachability set
0 references
vector addition systems
0 references
communicating finite state machines
0 references
0.8722745776176453
0 references
0.8288373351097107
0 references
0.8056488633155823
0 references
0.8056488037109375
0 references
