A multiparameter analysis of the boundedness problem for vector addition systems
type: Item
instance of: scholarly article
title: A multiparameter analysis of the boundedness problem for vector addition systems
zbMATH Open document ID: 0614.68048
DOI: 10.1016/0022-0000(86)90006-1
author: Louis E. Rosier
author: Hsu-Chun Yen
published in: Journal of Computer and System Sciences
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q85
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3995066
zbMATH Keywords: complexity of the boundedness problem
zbMATH Keywords: reachability set
zbMATH Keywords: vector addition systems
zbMATH Keywords: communicating finite state machines
MaRDI profile type: Publication
full work available at URL: 0022-0000(86)90006-1
OpenAlex ID: W2066238373
cites work: Bounds on Positive Integral Solutions of Linear Diophantine Equations
cites work: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
cites work: Q4198056
cites work: Q3780411
cites work: Priority Networks of Communicating Finite State Machines
cites work: On the reachability problem for 5-dimensional vector addition systems
cites work: Q3862379
cites work: Complexity of some problems in Petri nets
cites work: Gradually intractable problems and nondeterministic log-space lower bounds
cites work: Parallel program schemata
cites work: Q3048571
cites work: The complexity of the word problems for commutative semigroups and polynomial ideals
cites work: Q5590814
cites work: Q3911403
cites work: The covering and boundedness problems for vector addition systems
cites work: Q3685206
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Unboundedness detection for a class of communicating finite-state machines
description: scientific article; zbMATH DE number 3995066