  We introduce a new form of SAT-based symbolic model checking. One common idea
in SAT-based symbolic model checking is to generate new clauses from states
that can lead to property violations. Our previous work suggests applying
induction to generalize from such states. While effective on some benchmarks,
the main problem with inductive generalization is that not all such states can
be inductively generalized at a given time in the analysis, resulting in long
searches for generalizable states on some benchmarks. This paper introduces the
idea of inductively generalizing states relative to $k$-step
over-approximations: a given state is inductively generalized relative to the
latest $k$-step over-approximation relative to which the negation of the state
is itself inductive. This idea motivates an algorithm that inductively
generalizes a given state at the highest level $k$ so far examined, possibly by
generating more than one mutually $k$-step relative inductive clause. We
present experimental evidence that the algorithm is effective in practice.

Discrete Mathematics;Logic in Computer Science