State space (dynamical system)

State space (dynamical system)

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 [NASG] 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:

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

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Dynamical system — This article is about the general aspects of dynamical systems. For technical details, see Dynamical system (definition). For the study, see Dynamical systems theory. Dynamical redirects here. For other uses, see Dynamics (disambiguation). The… …   Wikipedia

  • Dynamical system (definition) — This article presents the many ways to define a dynamical system. See the main article, dynamical system, for an overview of the topic. The dynamical system concept is a mathematical formalization for any fixed rule which describes the time… …   Wikipedia

  • 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. To abstract from the number of inputs, outputs and… …   Wikipedia

  • Linear dynamical system — In a linear dynamical system, the variation of a state vector (an N dimensional vector denoted mathbf{x}) equals a constant matrix(denoted mathbf{A}) multiplied by mathbf{x}. This variation can take two forms: either as a flow, in which mathbf{x} …   Wikipedia

  • Dynamical systems theory — is an area of applied mathematics used to describe the behavior of complex dynamical systems, usually by employing differential equations or difference equations. When differential equations are employed, the theory is called continuous dynamical …   Wikipedia

  • Sequential dynamical system — Sequential dynamical systems (SDSs) are a class of discrete dynamical systems which generalize many aspects of systems such as cellular automata, and provide a framework for studying dynamical processes over graphs. SDSs are used in the analysis… …   Wikipedia

  • Dynamical billiards — The Bunimovich stadium is a chaotic dynamical billiard A billiard is a dynamical system in which a particle alternates between motion in a straight line and specular reflections from a boundary. When the particle hits the boundary it reflects… …   Wikipedia

  • State variable — A state variable is an element of the set of variables that describe the state of a dynamical system.In case of simple mechanical systems, position coordinates and their derivates are typical state variables. Temperature, pressure, internal… …   Wikipedia

  • State-transition matrix — In control theory, the state transition matrix is a matrix whose product with the state vector x at an initial time t 0 gives x at a later time t. The state transition matrix can be used to obtain the general solution of linear dynamical… …   Wikipedia

  • Dynamical time scale — has two distinct meanings and usages, both related to astronomy: In one use, which occurs in stellar physics, the dynamical time scale is alternatively known as the freefall time scale, and is in general, the length of time over which changes in… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”