Atomic proposition 2026-10-31
An indivisible statement treated as either true or false. In a labelled transition system, an atomic proposition holds at state exactly when .
Greatest fixed point 2026-10-31
A fixed point of a function on a partially ordered set that is greater than or equal to every other fixed point. For the order-preserving function on the power set of a finite transition system with no terminal states, its greatest fixed point is the set of states from which every infinite path in a transition system remains in . Iteration from the whole state space decreases to this set; every strict decrease removes at least one state.
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 define
The 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 , is
The 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.
Figure 1.
Four-state transition system with current bits (u, x), next bits (y, z), and relation y or (x and z)
. Details.
Every state has at least one successor, so for every . Therefore
The empty set is always a fixed point. Whenever is nonempty, it is therefore an additional, distinct fixed point.
For an explicit example, take a one-state transition system with , the self-loop , and . Then and has the two distinct fixed points and . This example meets the requirement of no terminal states.
The wording does not guarantee distinct additional fixed points for every instance. For example, if , then for every and its only fixed point is . Thus additional fixed points can occur, but need not occur. The universal example is distinct precisely when the desired satisfaction set is nonempty, as also follows from the greatest fixed point argument below.
Satisfaction set Created 2026-10-31 Updated 2026-11-05
For a state formula in a fixed labelled transition system, its satisfaction set is . This is a set of states; it is distinct from the assertion that every initial state satisfies the formula.
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]
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 is
Iterating 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.