State space (computer science)

In computer science, a state space is a description of a configuration of discrete states used as a simple model of machines. Formally, it can be defined as a tuple [N, A, S, G] where:

N is a set of states
A is a set of arcs connecting the states
S is a nonempty subset of N that contains start states
G is a nonempty subset of N that contains the goal states.

The state space is what state space search searches in. Graph theory is helpful in understanding and reasoning about state spaces.

A state space has some common properties:

complexity, where branching factor is important
structure of the space, see also graph theory:
- directionality of arcs
- tree
- rooted graph

State space (controls) for information about continuous state space in control engineering.
State space (physics) for information about continuous state space in physics.
Phase space for information about phase state (like continuous state space) in physics and mathematics.
Probability space for information about state space in probability.

See also