State space (dynamical system)
||This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. (February 2012)|
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.
- 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
- rooted graph
In a computer program, when the effective state space[clarification needed] is small compared to all reachable states, this is referred to as clumping.[examples needed] 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
- Dynamical systems for information about "state space" with a dynamical systems model of cognition.
- 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 978-0-387-98832-0