Package org.sosy_lab.java_smt.example

Class HoudiniApp

java.lang.Object

org.sosy_lab.java_smt.example.HoudiniApp

public class HoudiniApp
extends Object

This application executes the inductive-invariant synthesis algorithm called "Houdini" taken from the paper Flanagan and Leino: "Houdini, an Annotation Assistant for ESC/Java".

It considers a program manipulating a set X of variables, defined by an initial condition I(X) (given as lemmas) and a transition relation T(X, X'). Both I and T are quantifier-free first-order formulas.

A lemma F is called inductive with respect to T if it implies itself over the primed variables after the transition: FORALL X, X' . IMPLIES( AND( F(X), T(X, X') ), F(X')) i.e. in other words, the formula AND( F(X), T(X, X'), NOT(F(X')) ) is unsatisfiable.

The Houdini algorithm finds and returns a maximal inductive subset L_I of a given set L of candidate lemmas. It repeatedly checks the conjunction of L for inductiveness and updates L to exclude the lemmas that give rise to counterexamples-to-induction.

Constructor Summary

Constructors

Constructor	Description
HoudiniApp(SolverContext solverContext)

Method Summary

Modifier and Type	Method	Description
List<BooleanFormula>	houdini(List<BooleanFormula> lemmas, BooleanFormula transition)	execute the Houdini algorithm to get the maximal inductive subset L_I for the given lemmas and the transition.
static void	main(String... args)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

HoudiniApp

public HoudiniApp(SolverContext solverContext)

Method Detail

main

public static void main(String... args)
                 throws InvalidConfigurationException,
                        SolverException,
                        InterruptedException

Throws:

InvalidConfigurationException

SolverException

InterruptedException

houdini

public List<BooleanFormula> houdini(List<BooleanFormula> lemmas,
                                    BooleanFormula transition)
                             throws SolverException,
                                    InterruptedException

execute the Houdini algorithm to get the maximal inductive subset L_I for the given lemmas and the transition.

Throws:

SolverException

InterruptedException