On Selective Unboundedness of VASS

Stéphane Demri
(LSV, CNRS, ENSC, INRIA, France)

Numerous properties of vector addition systems with states amount to checking the (un)boundedness of some selective feature (e.g., number of reversals, run length). Some of these features can be checked in exponential space by using Rackoff's proof or its variants, combined with Savitch's theorem. However, the question is still open for many others, e.g., reversal-boundedness. In the paper, we introduce the class of generalized unboundedness properties that can be verified in exponential space by extending Rackoff's technique, sometimes in an unorthodox way. We obtain new optimal upper bounds, for example for place-boundedness problem, reversal-boundedness detection (several variants exist), strong promptness detection problem and regularity detection. Our analysis is sufficiently refined so as we also obtain a polynomial-space bound when the dimension is fixed.

In Yu-Fang Chen and Ahmed Rezine: Proceedings 12th International Workshop on Verification of Infinite-State Systems (INFINITY 2010), Singapore, 21st September 2010, Electronic Proceedings in Theoretical Computer Science 39, pp. 1–15.
Published: 28th October 2010.

ArXived at: http://dx.doi.org/10.4204/EPTCS.39.1 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org