Model Checking and the State-Space Explosion
Given a finite model and a temporal property, a checker explores every reachable state or proves it need not. The states multiply with every component, so the whole craft is abstraction: shrink the model until the check finishes while the property still means what it did.
What a learner can do afterwards
- Explain how a checker returns a counterexample trace and why that trace is the useful output
- Say why the state count grows with components and name two ways to cut it
- Say what an abstraction has to preserve for a passing check to say anything about the real system
1 · Read
A model checker takes a finite model and a property about how it behaves over time. It explores every reachable state, looking for a path that breaks the property. When it finds one, it hands you that path as a counterexample trace.
The counterexample trace is the useful output. It is a concrete run of your model that ends in the bug, so you can read it back as a flaw in the design and fix the design itself.
States multiply with every component you add, and the check soon cannot finish. The whole craft is abstraction: shrink the model until the check finishes, while keeping the property meaning what it did. Two cuts that respect this are hiding detail the property never mentions and merging states the property cannot tell apart.
An abstraction must preserve the property for a passing check to say anything about the real system. If the small model passes but the property changed meaning, you proved nothing.
Explore every state, read the counterexample as the bug, and shrink the model with abstractions that keep the property intact.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.