MODEL-CHECKING
MODEL-CHECKING is a computer science technique for the FORMAL-VERIFICATION of systems. It involves an automated process of checking whether a finite-state model of a system satisfies a given specification, usually formulated in TEMPORAL-LOGIC. This field was significantly advanced by the work of EDMUND-CLARKE, E-ALLEN-EMERSON, and JOSEPH-SIFAKIS, who were awarded the Turing Award for their contributions. The primary advantage of this approach is that it can provide a counterexample if the property is violated, which is invaluable for debugging complex CONCURRENT-SYSTEMS.
A major obstacle in MODEL-CHECKING is the STATE-EXPLOSION-PROBLEM, where the number of possible states in a system increases exponentially with the number of variables and components. To address this, various techniques have been developed, including SYMBOLIC-MODEL-CHECKING, which uses BINARY-DECISION-DIAGRAMS to represent state sets efficiently, and BOUNDED-MODEL-CHECKING, which leverages the power of SAT-SOLVERS. Modern tools such as the SPIN-MODEL-CHECKER, developed by GERARD-HOLZMANN, and NUV-SMV are widely used in both industry and academia.
Specifications are often written in LINEAR-TEMPORAL-LOGIC (LTL) or COMPUTATION-TREE-LOGIC (CTL). These logics allow for the expression of safety properties, which state that something bad never happens, and liveness properties, which state that something good eventually happens. For further reading, see the Wikipedia entry on Model Checking and the Stanford Encyclopedia of Philosophy on Formal Methods.