Download PDFOpen PDF in browserModel Based Interpolation for Uninterpreted Functions and Integer Linear ArithmeticEasyChair Preprint 1000021 pages•Date: May 7, 2023AbstractInterpolants are central for symbolic model-checking and synthesis of invariants in program verification. Over the past couple of decades several methods have been developed for extracting interpolants from proofs. They benefit from close proof theoretic connections between interpolants and proofs, but require a theorem prover to produce proof objects in a format the interpolation procedure understands. It adds a dependency between interpolation procedures and proof formats of the automated theorem prover. Can the dependency on proof objects be relaxed for interpolant generation? Model-based interpolation generation relies on exchanging models of formulas and unsatisfiable cores. We develop an algorithm for model-based interpolation for the theory of quantifier-free integer linear arithmetic with uninterpreted functions. The setting extends previous results for linear real arithmetic and uninterpreted functions, but in contrast to the linear real case cannot rely on uniform interpolation. Keyphrases: SMT, Uninterpreted Functions, arithmetic, automated theorem proving, interpolation
|