Deriving Invariants by Algorithmic Learning, Decision Procedures, and Predicate Abstraction

Download Now Date Added: Oct 2009
Format: PDF

Algorithmic learning has been applied to assumption generation in compositional reasoning. In contrast to traditional techniques, the learning approach does not derive assumptions in an off-line manner. It instead finds assumptions by interacting with a model checker progressively. Since assumptions in compositional reasoning are generally not unique, algorithmic learning can exploit the flexibility in assumptions to attain preferable solutions. Applications in formal verification and interface synthesis have also been reported. Finding loop invariants follows a similar pattern. Invariants are often not unique. Indeed, programmers derive invariants incrementally. They usually have their guesses of invariants in mind, and gradually refine their guesses by observing program behavior more.