Long-run average behavior of vector addition systems with states

K. Chatterjee, T.A. Henzinger, J. Otop, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 27.

Download
OA 538.12 KB

Conference Paper | Published | English
Series Title
LIPIcs
Abstract
A vector addition system with states (VASS) consists of a finite set of states and counters. A configuration is a state and a value for each counter; a transition changes the state and each counter is incremented, decremented, or left unchanged. While qualitative properties such as state and configuration reachability have been studied for VASS, we consider the long-run average cost of infinite computations of VASS. The cost of a configuration is for each state, a linear combination of the counter values. In the special case of uniform cost functions, the linear combination is the same for all states. The (regular) long-run emptiness problem is, given a VASS, a cost function, and a threshold value, if there is a (lasso-shaped) computation such that the long-run average value of the cost function does not exceed the threshold. For uniform cost functions, we show that the regular long-run emptiness problem is (a) decidable in polynomial time for integer-valued VASS, and (b) decidable but nonelementarily hard for natural-valued VASS (i.e., nonnegative counters). For general cost functions, we show that the problem is (c) NP-complete for integer-valued VASS, and (d) undecidable for natural-valued VASS. Our most interesting result is for (c) integer-valued VASS with general cost functions, where we establish a connection between the regular long-run emptiness problem and quadratic Diophantine inequalities. The general (nonregular) long-run emptiness problem is equally hard as the regular problem in all cases except (c), where it remains open.
Publishing Year
Date Published
2019-08-01
Volume
140
Article Number
27
Conference
CONCUR: International Conference on Concurrency Theory
Conference Location
Amsterdam, Netherlands
Conference Date
2019-08-27 – 2019-08-30
IST-REx-ID

Cite this

Chatterjee K, Henzinger TA, Otop J. Long-run average behavior of vector addition systems with states. In: Vol 140. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:27. doi:10.4230/LIPICS.CONCUR.2019.27
Chatterjee, K., Henzinger, T. A., & Otop, J. (2019). Long-run average behavior of vector addition systems with states (Vol. 140, p. 27). Presented at the CONCUR: International Conference on Concurrency Theory, Amsterdam, Netherlands: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.CONCUR.2019.27
Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Long-Run Average Behavior of Vector Addition Systems with States,” 140:27. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.CONCUR.2019.27.
K. Chatterjee, T. A. Henzinger, and J. Otop, “Long-run average behavior of vector addition systems with states,” presented at the CONCUR: International Conference on Concurrency Theory, Amsterdam, Netherlands, 2019, vol. 140, p. 27.
Chatterjee K, Henzinger TA, Otop J. 2019. Long-run average behavior of vector addition systems with states. CONCUR: International Conference on Concurrency Theory, LIPIcs, vol. 140. 27.
Chatterjee, Krishnendu, et al. Long-Run Average Behavior of Vector Addition Systems with States. Vol. 140, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 27, doi:10.4230/LIPICS.CONCUR.2019.27.
All files available under the following license(s):
Creative Commons License:
CC-BYCreative Commons Attribution 4.0 International Public License (CC-BY 4.0)
Main File(s)
File Name
Access Level
OA Open Access
Last Uploaded
2019-09-27T12:09:35Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar