In the theory of discrete dynamical systems, a state space is a directed graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

 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

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

 as a simple model of machines. Formally, a state space can be defined as a tuple

Tuple

In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...

 [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
  Subset
  In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
  
   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
  Branching factor
  In computing, tree data structures, and game theory, the branching factor is the number of children at each node. If this value is not uniform, an average branching factor can be calculated....
  
   is important
• structure of the space, see also graph theory
  Graph theory
  In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
  
  :
  • directionality of arcs
  • tree
  • rooted graph
    Rooted graph
    In mathematics, and, in particular, in graph theory, a rooted graph is a mathematical graph in which one node is labelled in a special way to distinguish it from the graph's other nodes. This special node is called the root of the graph....
    
    

In a computer program

Computer program

A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...

, when the effective state space is small compared to all reachable states

State (computer science)

In computer science and automata theory, a state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers....

, this is referred to as clumping. Software such as LURCH

LURCH

LURCH is a tool for software design debugging that uses a nondeterministic algorithm to quickly explore the reachable states of a software model...

 analyzes such situations.

State space search

State space search

State space search is a process used in the field of computer science, including artificial intelligence , in which successive configurations or states of an instance are considered, with the goal of finding a goal state with a desired property....

 explores a state space.

See also

• State space (controls)
  State space (controls)
  In control engineering, a state space representation is a mathematical model of a physical system as a set of input, output and state variables related by first-order differential equations...
  
   for information about continuous state space in control engineering.
• State space (physics)
  State space (physics)
  In physics, a state space is a complex Hilbert space within which the possible instantaneous states of the system may be described by a unit vector. These state vectors, using Dirac's bra-ket notation, can often be treated as vectors and operated on using the rules of linear algebra...
  
   for information about continuous state space in physics.
• Phase space
  Phase space
  In mathematics and physics, a phase space, introduced by Willard Gibbs in 1901, is a space in which all possible states of a system are represented, with each possible state of the system corresponding to one unique point in the phase space...
  
   for information about phase state (like continuous state space) in physics and mathematics.
• Probability space
  Probability space
  In probability theory, a probability space or a probability triple is a mathematical construct that models a real-world process consisting of states that occur randomly. A probability space is constructed with a specific kind of situation or experiment in mind...
  
   for information about state space in probability.
• Game complexity
  Game complexity
  Combinatorial game theory has several ways of measuring game complexity. This article describes five of them: state-space complexity, game tree size, decision complexity, game-tree complexity, and computational complexity.-Measures of game complexity:...
  
  theory, which relies on the state space of game outcomes