State space (dynamical system)
From Wikipedia, the free encyclopedia
(Redirected from State space)
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[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.
[edit] 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
[edit] 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