Skip to Main content Skip to Navigation

Transitive Closures of Affine Integer Tuple Relations and their Overapproximations

Sven Verdoolaege 1 Albert Cohen 1 Anna Beletska 1 
1 ALCHEMY - Architectures, Languages and Compilers to Harness the End of Moore Years
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
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. 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.
Complete list of metadata

Cited literature [37 references]  Display  Hide  Download
Contributor : Sven Verdoolaege Connect in order to contact the contributor
Submitted on : Friday, March 18, 2011 - 11:16:32 AM
Last modification on : Sunday, June 26, 2022 - 11:53:35 AM
Long-term archiving on: : Thursday, November 8, 2012 - 12:10:16 PM


Files produced by the author(s)


  • HAL Id : inria-00578052, version 1



Sven Verdoolaege, Albert Cohen, Anna Beletska. Transitive Closures of Affine Integer Tuple Relations and their Overapproximations. [Research Report] RR-7560, INRIA. 2011. ⟨inria-00578052⟩



Record views


Files downloads