State space

In computer science, a state space is a description of a configuration of 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

See also

• State space (controls) for information about state space in control engineering.