Computer Science – Logic in Computer Science
Scientific paper
2010-11-03
Computer Science
Logic in Computer Science
extended version (including proofs, complete rules listings, etc) of a VMCAI 2011 proceedings version
Scientific paper
Craig interpolation has emerged as an effective means of generating candidate program invariants. We present interpolation procedures for the theories of Presburger arithmetic combined with (i) uninterpreted predicates (QPA+UP), (ii) uninterpreted functions (QPA+UF) and (iii) extensional arrays (QPA+AR). We prove that none of these combinations can be effectively interpolated without the use of quantifiers, even if the input formulae are quantifier-free. We go on to identify fragments of QPA+UP and QPA+UF with restricted forms of guarded quantification that are closed under interpolation. Formulae in these fragments can easily be mapped to quantifier-free expressions with integer division. For QPA+AR, we formulate a sound interpolation procedure that potentially produces interpolants with unrestricted quantifiers.
Brillout Angelo
Kroening Daniel
Ruemmer Philipp
Wahl Thomas
No associations
LandOfFree
Beyond Quantifier-Free Interpolation in Extensions of Presburger Arithmetic (Extended Technical Report) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Beyond Quantifier-Free Interpolation in Extensions of Presburger Arithmetic (Extended Technical Report), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Beyond Quantifier-Free Interpolation in Extensions of Presburger Arithmetic (Extended Technical Report) will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-145175