Abhik Roychoudhury

SUNY Stony Brook


Model Checking Parameterized Systems using Tabled Resolution

Room 2C-542
February 26, 1998 at 12:30 PM

Abstract:

Incorporation of tabling in logic programming systems (as in XSB developed at SUNY Stony Brook) has been shown to yield efficient programmable fixed-point engines. Recently, such a tabled LP system was used for constructing a succinct and efficient local model-checker for finite state systems.

In this talk, we describe how tabled resolution can be extended to perform model-checking of parameterized systems. In particular, we introduce "Abstract Resolution" which can be used for model-checking an infinite family of finite state systems. Abstract resolution thus can enable a tabled LP system to skip over infinite computations and derive answers conditional on the success or failure of skipped computations. It also extensively uses a deductive technique known as folding, i.e. replacing instances of clause bodies with corresponding instances of clause heads. Together, these mechanisms allow abstract resolution to construct explicit induction proofs of parameterized systems in a highly automated fashion.