An interpolating decision procedure for transitive relations with uninterpreted functions

We present a proof-generating decision procedure for the quantifier-free fragment of first-order logic with the relations =, !=, >=, and > and argue that this logic, augmented with a set of theory-specific rewriting rules, is adequate for bit-level accurate verification. We describe ou...

Popoln opis

Bibliografske podrobnosti
Main Authors: Kroening, D, Weissenbacher, G
Drugi avtorji: Namjoshi, K
Format: Book section
Jezik:English
Izdano: 2009
Teme:
Opis
Izvleček:We present a proof-generating decision procedure for the quantifier-free fragment of first-order logic with the relations =, !=, >=, and > and argue that this logic, augmented with a set of theory-specific rewriting rules, is adequate for bit-level accurate verification. We describe our decision procedure from an algorithmic point of view and explain how it is possible to efficiently generate Craig interpolants for this logic. Furthermore, we discuss the relevance of the logical fragmentin software model checking and provide a preliminary evaluation of its applicability using an interpolation-based program analyser.