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 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.
Famous quotes containing the words state and/or space:
“In the most high and palmy state of Rome,
A little ere the mightiest Julius fell,
The graves stood tenantless and the sheeted dead
Did squeak and gibber in the Roman streets.”
—William Shakespeare (1564–1616)
“But alas! I never could keep a promise. I do not blame myself for this weakness, because the fault must lie in my physical organization. It is likely that such a very liberal amount of space was given to the organ which enables me to make promises, that the organ which should enable me to keep them was crowded out. But I grieve not. I like no half-way things. I had rather have one faculty nobly developed than two faculties of mere ordinary capacity.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)