State space

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

See also

• 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.