conference paper
Faster algorithms for quantitative verification in constant treewidth graphs
LNCS
published
yes
Krishnendu
Chatterjee
author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X
Rasmus
Ibsen-Jensen
author 3B699956-F248-11E8-B48F-1D18A9856A870000-0003-4783-0389
Andreas
Pavlogiannis
author 49704004-F248-11E8-B48F-1D18A9856A870000-0002-8943-0722
KrCh
department
CAV: Computer Aided Verification
Modern Graph Algorithmic Techniques in Formal Verification
project
Rigorous Systems Engineering
project
Quantitative Graph Games: Theory and Applications
project
Microsoft Research Faculty Fellowship
project
We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff property, the ratio property, and the minimum initial credit for energy property. The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let n denote the number of nodes of a graph, m the number of edges (for constant treewidth graphs m=O(n)) and W the largest absolute value of the weights. Our main theoretical results are as follows. First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a multiplicative factor of ϵ in time O(n⋅log(n/ϵ)) and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time O(n⋅log(|a⋅b|))=O(n⋅log(n⋅W)), when the output is ab, as compared to the previously best known algorithm with running time O(n2⋅log(n⋅W)). Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in O(n2⋅m) time and the associated decision problem can be solved in O(n⋅m) time, improving the previous known O(n3⋅m⋅log(n⋅W)) and O(n2⋅m) bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires O(n⋅logn) time, improving the previous known O(n4⋅log(n⋅W)) bound. We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks.
Springer2015San Francisco, CA, USA
eng
10.1007/978-3-319-21690-4_9
9206140 - 157
https://research-explorer.app.ist.ac.at/record/5430 https://research-explorer.app.ist.ac.at/record/5437 https://research-explorer.app.ist.ac.at/record/821
Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. “Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs,” 9206:140–57. Springer, 2015. <a href="https://doi.org/10.1007/978-3-319-21690-4_9">https://doi.org/10.1007/978-3-319-21690-4_9</a>.
Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. Faster algorithms for quantitative verification in constant treewidth graphs. In: Vol 9206. Springer; 2015:140-157. doi:<a href="https://doi.org/10.1007/978-3-319-21690-4_9">10.1007/978-3-319-21690-4_9</a>
Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2015). Faster algorithms for quantitative verification in constant treewidth graphs (Vol. 9206, pp. 140–157). Presented at the CAV: Computer Aided Verification, San Francisco, CA, USA: Springer. <a href="https://doi.org/10.1007/978-3-319-21690-4_9">https://doi.org/10.1007/978-3-319-21690-4_9</a>
K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, in:, Springer, 2015, pp. 140–157.
Chatterjee, Krishnendu, et al. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. Vol. 9206, Springer, 2015, pp. 140–57, doi:<a href="https://doi.org/10.1007/978-3-319-21690-4_9">10.1007/978-3-319-21690-4_9</a>.
Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs. CAV: Computer Aided Verification, LNCS, vol. 9206, 140–157.
K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, “Faster algorithms for quantitative verification in constant treewidth graphs,” presented at the CAV: Computer Aided Verification, San Francisco, CA, USA, 2015, vol. 9206, pp. 140–157.
16072018-12-11T11:52:59Z2021-05-17T09:57:38Z