Formal methods 2026-11-05
Formal methods use mathematically defined models, specifications and reasoning techniques to describe and analyze systems. They include writing a formal specification, proving properties through formal verification, exploring a finite model by model checking and deriving information through static program analysis. A method's guarantee is relative to its model and assumptions.
For example, a loop summing an array can maintain the invariant that the current accumulator equals the sum of the entries already visited. Initialization, preservation by one iteration and the exit condition establish the returned sum; a separate termination argument shows that an answer is reached. Arithmetic and array bounds must be specified, since a proof using unbounded integers need not describe overflowing machine arithmetic.[ref]
Model checking Created 2026-10-31 Updated 2026-11-05
Model checking verifies whether a formally represented system satisfies a specified property, often a temporal logic formula over a finite transition system. A safety question asks whether a bad state is reachable; exhaustive state exploration can either find a counterexample path or establish its absence in the model. Symbolic model checking represents sets of states compactly, while bounded methods search executions up to a chosen horizon. Verification is relative to the model and assumptions: a missing physical behaviour is not ruled out merely because it was omitted from the transition relation.[ref]
State-space explosion 2026-11-05
State-space explosion is the rapid growth of a model's possible global configurations as its components are combined. If independent components each have two local states, their Cartesian product has global states. Thirty such components already permit combinations, before accounting for additional data values.
Model checking must establish a property over relevant reachable behavior, so checking one representative execution is insufficient. The reachable subset can be much smaller than the full product, and symbolic representations can compactly describe many configurations at once. However, compactness depends on structure; it is not a universal removal of exponential difficulty. The practical aim is to exploit shared structure without omitting behavior needed for the claimed formal verification.[ref]