formalmethods.dev

§ 1.2

Kripke structures

The machine you *intend* to build, written so a machine can read it.

see also · Model checking · Bounded model checking

States, labels, transitions

A Kripke structure is a directed graph: states, each labelled with the atomic propositions true there; transitions say which state may follow which; initial states say where runs begin.

That is deliberately less than real code says — no variables, no clocks. Modelling is abstraction: keep exactly enough to state what correct means.

Nondeterminism is a feature

A state with two outgoing transitions does not choose — the environment does. Checking the structure checks every resolution, so an adversary is covered before it exists.

Dead ends stutter forever (the system has frozen). That one convention is what lets liveness properties catch hangs.

try it · draw and check a structure — lab B →