Niveau: Supérieur, Doctorat, Bac+8
Abstract Interpretation Frameworks Patrick Cousot LIENS, École Normale Supérieure 45, rue d'Ulm 75230 Paris cedex 05 (France) Radhia Cousot LIX, École Polytechnique 91128 Palaiseau cedex (France) Abstract We introduce abstract interpretation frameworks which are variations on the archetypal framework using Galois connections between concrete and abstract semantics, widenings and narrowings and are obtained by relaxation of the original hypotheses. We consider various ways of establishing the correctness of an abstract interpretation depending on how the relation between the concrete and abstract semantics is defined. We insist upon those correspondences allowing for the inducing of the approximate abstract semantics from the concrete one. Furthermore we study various notions of widening and narrowing as a means of obtaining convergence in the iterations used in abstract interpretation. Keywords: Abstract interpretation; standard and collecting semantics; concrete and abstract se? mantics; discrete approximation; soundness relation; abstraction; concretization; Galois connections; widening; narrowing; 1 Introduction The semantics of programs describes the set of all possible behaviours of these pro? grams when executed for all possible input data. For example, these behaviours can be non-termination, termination with an error or correct termination delivering one or more output results. Abstract interpretation is a method for designing approximate semantics of pro? grams which can be used to gather information about programs in order to provide sound answers to questions about their run-time behaviours.
- abstract interpretation
- join ?
- transition relation
- concrete semantics
- chart programs
- programs
- partial order
- distinction between
- semantics