Skip to Main content Skip to Navigation
Conference papers

Constraint-based reachability

Abstract : Iterative imperative programs can be considered as infinite-state systems computing over possibly unbounded domains. Studying reachability in these systems is challenging as it requires to deal with an infinite number of states with standard backward or forward exploration strategies. An approach that we call {\it Constraint-based reachability}, is proposed to address reachability problems by exploring program states using a constraint model of the whole program. The keypoint of the approach is to interpret imperative constructions such as conditionals, loops, array and memory manipulations with the fundamental notion of {\it constraint} over a computational domain. By combining constraint filtering and abstraction techniques, {\it Constraint-based reachability} is able to solve reachability problems which are usually outside the scope of backward or forward exploration strategies. This paper proposes an interpretation of classical filtering consistencies used in Constraint Programming as abstract domain computations, and shows how this approach can be used to produce a constraint solver that efficiently generates solutions for reachability problems that are unsolvable by other approaches.
Document type :
Conference papers
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-00807856
Contributor : Arnaud Gotlieb <>
Submitted on : Thursday, April 4, 2013 - 3:01:09 PM
Last modification on : Monday, July 27, 2020 - 10:32:02 AM
Document(s) archivé(s) le : Friday, July 5, 2013 - 4:18:09 AM

File

GotliebDenmatLazaar_Infinity20...
Files produced by the author(s)

Identifiers

Citation

Arnaud Gotlieb, Tristan Denmat, Nadjib Lazaar. Constraint-based reachability. Infinity workshop 2012, Aug 2012, Paris, France. ⟨10.4204/EPTCS.107.4⟩. ⟨hal-00807856⟩

Share

Metrics

Record views

588

Files downloads

278