Bounded semantics based correctness checking for extended ECTL∗ properties

摘要

Bounded model checking based on bounded semantics is an efficient method for finding errors in system designs. The basic idea of the bounded semantics for temporal logics (or fragments of such logics) is to consider bounded paths (possibly with loops) instead of all of the infinite ones. In this paper, we further study bounded semantics of extended ECTL* (eECTL*) formulas which allows some sort of fairness that are not supported by some well known model checkers such as Spin and NuSMV. A QBF encoding of this logic is then developed from the definition of the bounded semantics. Finally, we propose a bounded correctness checking algorithm for eECTL* formulas and apply the bounded semantics of eECTL* to derive a QBF-based characterization of eECTL* properties.