Technical Report No. 201 - Abstract

Tobias Nopper, Christoph Scholl
Symbolic Model Checking for Incomplete Designs

We consider the problem of checking whether an incomplete design can still be extended to a complete design satisfying a given CTL formula and whether the property is satisfied for all possible extensions. Motivated by the fact that well-known model checkers like SMV or VIS produce incorrect results when handling unknowns by using the programs' non-deterministic signals, we present a series of approximate, yet sound algorithms to process incomplete designs with increasing quality and computational resources. Furthermore, we present an exact algorithm to process incomplete designs in which for each unknown area a fixed upper bound on the number of internal states is assumed and an approximate, yet sound method based on this. Finally we give a series of experimental results demonstrating the effectiveness and feasibility of the presented methods.