Author(s):

Brázdil, Tomáš; Chatterjee, Krishnendu; Kučera, Antonín; Novotný, Petr; Velan, Dominik; Zuleger, Florian

Title: 
Efficient algorithms for asymptotic bounds on termination time in VASS

Title Series: 
ACM/IEEE Symposium on Logic in Computer Science

Affiliation 
IST Austria 
Abstract: 
Vector Addition Systems with States (VASS) provide a wellknown and fundamental model for the analysis of concurrent processes, parameterized systems, and are also used as abstract models of programs in resource bound analysis. In this paper we study the problem of obtaining asymptotic bounds on the termination time of a given VASS. In particular, we focus on the practically important case of obtaining polynomial bounds on termination time. Our main contributions are as follows: First, we present a polynomialtime algorithm for deciding whether a given VASS has a linear asymptotic complexity. We also show that if the complexity of a VASS is not linear, it is at least quadratic. Second, we classify VASS according to quantitative properties of their cycles. We show that certain singularities in these properties are the key reason for nonpolynomial asymptotic complexity of VASS. In absence of singularities, we show that the asymptotic complexity is always polynomial and of the form Θ(nk), for some integer k d, where d is the dimension of the VASS. We present a polynomialtime algorithm computing the optimal k. For general VASS, the same algorithm, which is based on a complete technique for the construction of ranking functions in VASS, produces a valid lower bound, i.e., a k such that the termination complexity is (nk). Our results are based on new insights into the geometry of VASS dynamics, which hold the potential for further applicability to VASS analysis.

Keywords: 
Asymptotic complexity; Polynomial approximation; Polynomialtime algorithms; Vectors; Vector addition systems; Computer circuits; Asymptotic bounds; Concurrent process; Fundamental models; Parameterized system; Resource bound analysis

Conference Title:

LICS: Logic in Computer Science

Volume: 
Part F138033

Conference Dates:

9  12 July, 2018

Conference Location:

Oxford, UK

ISBN:

10436871 (ISSN); 9781450355834 (ISBN); 9781450355834 (ISBN)

Publisher:

IEEE

Date Published:

20180709

Start Page: 
185

End Page:

194

DOI: 
10.1145/3209108.3209191

Open access: 
no 