Transitive Closures of Affine Integer Tuple Relations and their Overapproximations

Sven Verdoolaege 1 Albert Cohen 1 Anna Beletska 2
1 Parkas - Parallélisme de Kahn Synchrone
CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria Paris-Rocquencourt, DI-ENS - Département d'informatique de l'École normale supérieure
2 ALCHEMY - Architectures, Languages and Compilers to Harness the End of Moore Years
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France
Abstract : The set of paths in a graph is an important concept with many applications in system analysis. In the context of integer tuple relations, which can be used to represent possibly infinite graphs, this set corresponds to the transitive closure of the relation representing the graph. Relations described using only affine constraints and projection are fairly efficient to use in practice and capture Presburger arithmetic. Unfortunately, the transitive closure of such a quasi-affine relation may not be quasi-affine and so there is a need for approximations. In particular, most applications in system analysis require overapproximations. Previous work has mostly focused either on underapproximations or special cases of affine relations. We present a novel algorithm for computing overapproximations of transitive closures for the general case of quasi-affine relations (convex or not). Experiments on non-trivial relations from real-world applications show our algorithm to be on average more accurate and faster than the best known alternatives.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [33 references]  Display  Hide  Download

https://hal.inria.fr/hal-00645221
Contributor : Albert Cohen <>
Submitted on : Tuesday, November 29, 2011 - 11:48:36 AM
Last modification on : Thursday, February 7, 2019 - 3:49:36 PM
Document(s) archivé(s) le : Monday, December 5, 2016 - 8:59:37 AM

File

sas.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Sven Verdoolaege, Albert Cohen, Anna Beletska. Transitive Closures of Affine Integer Tuple Relations and their Overapproximations. SAS 2011 - The 18th International Static Analysis Symposium, Sep 2011, Venice, Italy. pp.216-232, ⟨10.1007/978-3-642-23702-7_18⟩. ⟨hal-00645221⟩

Share

Metrics

Record views

1138

Files downloads

229