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