Computation tree logic 2026-10-31
A branching temporal logic whose operators quantify over paths in a transition system from a state. In particular, , also written , holds at when every infinite path in a transition system from satisfies at every position, including its initial position.
Linear temporal logic 2026-10-31
A temporal logic interpreted along infinite paths in a transition system. At position , requires at , requires it at some , and requires it at every . Strong until and weak until express conditions that hold up to a later event. A system satisfies a specification when all relevant initial paths in a transition system satisfy it.
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]
https://www.cs.cmu.edu/~modelcheck/. CMU model-checking group, finite-state verification and temporal specifications
Temporal logic Created 2026-10-31 Updated 2026-11-05
Temporal logic extends ordinary mathematical logic with assertions about successive states or times. Temporal operators express properties such as eventually holding, always holding, or holding until another condition occurs.
In linear temporal logic, says that every request is eventually answered along a trace. A safety property rules out a bad finite behavior; a liveness property requires future progress. Computation tree logic additionally distinguishes possible execution paths. The choice of linear or branching time determines exactly which system behaviors a formula quantifies over.
Temporal operator Created 2026-10-31 Updated 2026-11-05
A temporal operator states how a proposition behaves across time in a temporal logic. In linear temporal logic, means that holds at the next position, that it holds eventually, and that it holds at every later position, including the current one.
The binary strong until operator requires a future position where holds and requires at all earlier positions. Thus expresses that every request eventually gets a response. The temporal operators distinguish such behavior from an ordinary Boolean condition evaluated at one instant. Branching-time logics additionally quantify over possible execution paths.
Terminal state 2026-10-31
A state with no successor in the transition relation. Assuming no terminal states makes every finite path in a transition system extendible and avoids choosing a separate convention for interpreting infinite-path temporal logic at a dead end.