Patent ID: 7441216

Claim:
A method for applying conjunctive normal form simplification techniques to satisfiability-based abstraction refinement, to extract original clauses that generate simplified clauses, in a computer system, said method comprising: receiving a first Boolean formula, from a first memory location; generating a second Boolean formula by applying conjunctive normal form simplification technique to said first Boolean formula; generating book-keeping information during application of said simplification technique; generating a new formula, by abstracting said second Boolean formula; eliminating or adding clauses, based on said book-keeping information; running a satisfiability solver, in said computer system; wherein if said satisfiability solver returns a satisfiable result, then there is a counter-example; if said satisfiability solver returns a satisfiable result, doing refinement by adding more layers, wherein each added layer among said layers is for refinement, with partitions inserted to a model in said each added layer, from a first layer to a last layer; for said each added layer, repeating following steps, until an unsatisfiable result is obtained, or a satisfiable result on a concrete model is obtained: generating another formula, by abstracting a previous Boolean formula, eliminating or adding clauses, based on said book-keeping information, and running said satisfiability solver; if said satisfiability solver returns an unsatisfiable result, then identifying unsatisfiable core in last Boolean formula; and generating another unsatisfiable core using said book-keeping information, wherein clauses in the last layers are only from said first Boolean formula, and are the same as said first Boolean formula from the first layer, using a backward mapping scheme produced by a simplification mechanism, in order to extract the original clauses that generate the simplified clauses, by iterating generation and abstraction procedures to be used for another abstraction.