A transition relation requires an explicit interpretation of the Boolean variables as current and next state bits. Take the four states . Encode the current state by and the next state by , and defineThe extra current bit is deliberately unused by the Boolean formula. A four-state transition system normally needs four bits to describe a pair of states; a Boolean formula using only three of them simply describes a transition relation independent of the fourth bit.
When , the condition is , so the permitted next states are and . When , the condition is , so the permitted next states are . The resulting adjacency matrix, with rows and columns both ordered , isThe directed graph below plots all ten directed edges, including the three self-loops. No arrow enters , but it is a valid state with two outgoing arrows. Every state has a successor. As permitted, no initial states are distinguished.
To apply bounded model checking, seek an initial path in a transition system satisfyingA satisfying assignment for its bounded encoding is enough to disprove the specification. Use a lasso path: positions follow the transition relation, and a final arrow returns from to some , . The repeated part is . On such a lasso path, is equivalent to having true at some position of the repeated part.
For this example an explicit Boolean formula for the bounded search isHere means and means that the source diagram has the arrow ; each can be encoded by finite Boolean variables for the states. The loop requirements are the fairness assumption and the negated specification respectively. Unrolling the transition relation and adding a loop closure is the usual bounded model checking construction.[ref]
Symbolic Model Checking without BDDs by Armin Biere and others. §2, worked example with an unrolled transition relation and a returning loop; §3, infinite-path semantics
At bound , an initial self-loop would be needed. The only such choice is , whose repeated label satisfies and . It violates both loop requirements. The other initial state, , has no self-loop. Thus has no satisfying assignment.
At bound , chooseBoth required arrows and exist. At , is false and hence is false, so both repeated-part requirements are true. Equivalently, the label values are and . These values give a satisfying assignment of , representing the fair counterexample . ConsequentlyHere the bound counts forward arrows before the returning arrow, so stores two positions and describes a two-state repeated part. There is no need for a completeness bound: the exhibited fair counterexample settles the negative answer. These satisfying assignments are checked directly; no claim of executing an external SAT solver is needed.
State (computer science) 2026-10-31
A configuration of a system at one moment. In a transition system, a state is an element of its state space , and a transition relation specifies permitted changes of state.
State-space search 2026-11-05
A state-space search solves a problem by exploring a transition system: a state records the current situation, a transition relation specifies legal moves, and a goal state specifies success. The answer is usually a path in a transition system, rather than just the final configuration. This separates modeling the problem from choosing the search algorithm.
For a sliding-tile puzzle, the state is the arrangement of tiles and the empty square; one move slides a neighboring tile into that square. Breadth-first search finds a solution using the fewest moves when all moves have equal cost. Depth-first search can use less working storage but need not find a shortest solution. Remembering visited configurations prevents repeatedly exploring a cycle. The same formulation applies to route finding and automated planning.[ref]
Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig. Chapter 3, problem formulation and search strategies
Symbolic model checking 2026-11-05
Symbolic model checking verifies a Transition system by representing sets of states and transitions as formulas or decision structures rather than enumerating each state separately. Encode a current state by bits and its successor by bits . A formula describes the transition relation. If denotes currently reachable states, the next reachable set isIterating from the initial-state formula reaches a fixed point in a finite system. Intersecting that set with a bad-state formula checks a safety property.
Binary decision diagrams can make these operations compact when the represented Boolean structure is favorable. A system with Boolean state components has up to states, so sharing structure can be decisive. The representation can nevertheless become exponentially large, and variable ordering strongly affects a decision diagram's size. Symbolic representation mitigates state-space explosion; it does not abolish it.
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.
Transition relation 2026-10-31
A binary relation on the states of a system, with meaning that one permitted step changes to . A Boolean formula can encode a transition relation after choosing bits for the current and next states.
Transition system 2026-10-31
A model consisting of a set of states, a transition relation , initial states , a set of atomic propositions, and a label function identifying which atomic propositions hold at each state. A path in a transition system follows permitted transitions. Some definitions omit labels or initial conditions; specify the convention used in each application.
