State Space Partitioning¶

Why It Matters¶

Systems are too complex to reason about state-by-state. Partitioning lets you handle entire regions uniformly. It exposes structure: which states are reachable, which transitions are possible, where boundaries lie. Most critically, it forces you to think about the whole space, not just the states you've seen.

The Key Move¶

For any system, identify the state variables (what can vary). Partition the space by properties that matter: valid/invalid, reachable/unreachable, safe/unsafe, handled/unhandled. For each region, characterize the behavior. Check that you've covered the entire space and that regions don't overlap unexpectedly.

Classic Application¶

Model checking. To verify a hardware design, partition its state space into reachable and unreachable states. Then check that all reachable states satisfy safety properties. The key insight: you don't need to check unreachable states, and finding unexpectedly reachable dangerous states reveals design flaws.

Surprising Application¶

Life stage planning. Partition life not by age but by state: single/partnered, childless/parenting, employed/entrepreneurial/retired, renting/owning. This reveals that "age 35" isn't a meaningful category - people at 35 span many state regions with different constraints and opportunities. Plan by state region, not by age.

Failure Modes¶

Irrelevant partitions - dividing by properties that don't affect behavior. Too fine-grained - partitioning into so many regions you can't reason about them. Missing critical boundary cases that straddle partition lines. Assuming clean partitions when reality has messy overlaps.

Go Deeper¶

Baier & Katoen, Principles of Model Checking, Chapter 1; Clarke et al., Model Checking, Chapter 2