State space (dynamical system)

In the theory of discrete dynamical systems, a state space is a directed graph where each possible state of a dynamical system is represented by a vertex, and there is a directed edge from a to b if and only if ƒ(a) = b where the function f defines the dynamical system.

State spaces are useful in computer science as a simple model of machines. Formally, a state space 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.

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

In a computer program, when the effective state space is small compared to all reachable states, this is referred to as clumping. Software such as LURCH analyzes such situations.

State space search explores a state space.

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.
• Game complexity theory, which relies on the state space of game outcomes

References

• Equivalence Relations on Finite Dynamical Systems, Laubenbacher, R. Pareigis, B., ADVANCES IN APPLIED MATHEMATICS, 2001, VOL 26; PART 3, pages 237–251
• State-space search: algorithms, complexity, extensions, and applications, Weixiong Zhang, Springer, 1999, ISBN 9780387988320