Patent Document ID: 7519931
Application ID: 12250534
Patent Flag: 1

Claim One:
1. A system for applying conjunctive normal form simplification techniques to satisfiability-based abstraction refinement, to extract original clauses that generated simplified clauses, in a computer module, said system comprising: a first memory location; a satisfiability solver; wherein a first Boolean formula is received, from said first memory location; a second Boolean formula is generated by applying conjunctive normal form simplification technique to said first Boolean formula; book-keeping information is generated during application of said simplification technique; a new formula is generated, by abstracting said second Boolean formula; clauses are eliminated or added, based on said book-keeping information; said satisfiability solver is run, in said computer module; wherein if said satisfiability solver returns a satisfiable result, then there is a counter-example; if said satisfiability solver returns a satisfiable result, refinement is done by adding more layers; 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, following steps are repeated, 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 unsatisfiable core in last Boolean formula is identified; and another unsatisfiable core is generated using said book-keeping information, wherein clauses in the last layer 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 generated the simplified clauses, by iterating generation and abstraction procedures, to be used for another abstraction.