Learning the Boundary of Inductive Invariants
summary
An interpolation-based invariant inference algorithm with model-based generalization (dropping literals) uses bounded model checking to implement membership and inductiveness checks and runs in a polynomial number of iterations whenever an inductive invariant is k-fenced (the Hamming-boundary reaches bad states within k steps) and has a short monotone DNF or almost-monotone DNF representation. The work lifts Bshouty’s exact-learning results, extends to decision-tree forms under a two-sided fence, and shows renaming/combining preserves the fence while adding helper variables or replacing negations can break it.
AI-written summary · about