Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS

DOI10.1145/3209108.3209191MaRDI QIDQ5145291zbMATH OpenOpenAlexFDO

Authors Tomáš Brázdil, Krishnendu Chatterjee, Petr Novotný, Dominik Velan, Florian Zuleger, Antonin Kučera

Publication date 20 January 2021

Published in Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.10985

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: Vector Addition Systems with States (VASS) provide a well-known 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 polynomial-time 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 non-polynomial asymptotic complexity of VASS. In absence of singularities, we show that the asymptotic complexity is always polynomial and of the form $Theta(n^k)$, for some integer $kleqd$, where $d$ is the dimension of the VASS. We present a polynomial-time 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 $Omega(n^k)$. Our results are based on new insights into the geometry of VASS dynamics, which hold the potential for further applicability to VASS analysis.

Recommendations

• Deciding Polynomial Termination Complexity for VASS Programs
• Deciding fast termination for probabilistic VASS with nondeterminism
• A tight lower bound for the completion time variance problem
• On genuinely time bounded computations
• Faster exact algorithms for some terminal set problems
• Faster exact algorithms for some terminal set problems
• Time-approximation trade-offs for inapproximable problems
• Time-approximation trade-offs for inapproximable problems

Cited in

(10)

• Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States
• ATLAS: automated amortised complexity analysis of self-adjusting data structures
• Complexity analysis of the backward coverability algorithm for VASS
• On the existence and computability of long-run average properties in probabilistic VASS
• Long-Run Average Behavior of Vector Addition Systems with States
• The polynomial complexity of vector addition systems with states
• Introducing divergence for infinite probabilistic models
• Fast termination and workflow nets
• Deciding fast termination for probabilistic VASS with nondeterminism
• Type-based analysis of logarithmic amortised complexity

This page was built for publication: Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145291)