State space (computer science)

from Wikipedia, the free encyclopedia

In theoretical computer science , a state space is a description of discrete states in order to use them as a simple model of machines (e.g. finite automata ) (not to be confused with the state space (neural network) in neuroinformatics). Formally it is defined as a tuple [N, A, S, G] where:

  • N a set of states
  • A a set of transition edges between the states,
  • S is a non-empty subset of N that contains the starting nodes and
  • G is a non-empty subset of N that contains the target nodes.

The representation can take place via state transition diagrams . Graph theory is helpful in understanding state spaces .

A state space can be described with the following properties:

  • Complexity that a metric forms on a state space.
    This corresponds to the size of the set N. Often the state space is not restricted (e.g. with Turing machines ). Depending on the definition of the state space, this quantity is not always easy to determine.
  • Structure of space, see graph theory
    • The state space is a directed graph
    • Is the graph tree-like, or
    • is the graph a circle?

See also

Web links