Farkas-Based Tree Interpolation

Abstract:

Linear arithmetic over reals (LRA) underlies a wide range of SMT-based modeling approaches, and, strengthened with Craig interpolation using Farkas’ lemma, is a central tool for efficient over-approximation. Recent advances in LRA interpolation have resulted in a range of promising interpolation algorithms with so far poorly understood properties. In this work we study the Farkas-based algorithms with respect to tree interpolation, a practically important approach where a set of interpolants is constructed following a given tree structure. We classify the algorithms based on whether they guarantee the tree interpolation property, and present how to lift a recently introduced approach producing conjunctive LRA interpolants to tree interpolation in the quantifier-free LRA fragment of first-order logic. Our experiments show that the standard interpolation and the approach using conjunctive interpolants are complementary in tree interpolation, and suggest that their combination would be very powerful in practice.

BibTeX:

@inproceedings{asadi_farkasbased_2020,
    title = {{Farkas-Based Tree Interpolation}},
    author = {Asadi, Sepideh and Blicha, Martin and Hyvärinen, Antti and Fedyukovich, Grigory and Sharygina, Natasha},
    year = {2020},
    booktitle = {{Static Analysis}},
    editor = {Pichardie, David and Sighireanu, Mihaela},
    publisher = {Springer International Publishing},
    series = {{Lecture Notes in Computer Science}},
    location = {Cham},
    doi = {10.1007/978-3-030-65474-0_16},
    isbn = {978-3-030-65474-0},
    pages = {357--379},
}

Proceedings paper