State transition system

State transition system

In theoretical computer science, a state transition system is an abstract machine used in the study of computation. The machine consists of a set of states and transitions between states.

State transition systems differ from finite state automata in several ways:

* In a state transition system the set of states is not necessarily finite, or even countable.
* In a state transition system the set of transitions is not necessarily finite, or even countable.

State transition systems with a finite number of states and transitions can be represented as directed graphs.

There are at least two basic types of state transition systems: labelled (or LTS for "labelled transition system") or unlabelled.

Formal definition

Formally, an unlabelled state transition system is a tuple ("S", →) where "S" is a set (of states) and → ⊆ "S" × "S" is a binary relation over "S" (of transitions.) If "p", "q" ∈ "S", ("p", "q") ∈ → is usually written as "p" → "q". This represents the fact that there is a transition from state "p" to state "q".

A labelled transition system is a tuple ("S", Λ, →) where "S" is a set (of states), Λ is a set (of labels) and → ⊆ "S" × Λ × "S" is a ternary relation (of labelled transitions.) If "p", "q" ∈ "S" and α ∈ Λ, then ("p",α,"q") ∈ → is written as

: p overset{alpha}{ ightarrow} q. ,

This represents the fact that there is a transition from state "p" to state "q" with label α. Labels can represent different things depending on the language of interest. Typical uses of labels include representing input expected, conditions that must be true to trigger the transition, or actions performed during the transition.

Relation between labelled and unlabelled transition systems.

There are many relations between these concepts. Some are simple, such as observing that a labelled transition system where the set of labels consists of only one element is equivalent to an unlabelled transition system. However not all these relations are equally trivial.

See also

* Simulation preorder
* Bisimulation
* Operational semantics


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • State transition testing — State Transition TestingA system may exhibit a different response depending on current conditions and prevailing history. The state transition diagram allows the tester to view the software in terms of its states, transition between states, the… …   Wikipedia

  • State transition table — In automata theory and sequential logic, a state transition table is a table showing what state (or states in the case of a nondeterministic finite automaton) a finite semiautomaton or finite state machine will move to, based on the current state …   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

  • State diagram — State diagrams is a diagram used in the field of computer science, representing the behavior of a system, which is composed of a finite number of states. There are many forms of state diagrams, which differ slightly and have different semantics.… …   Wikipedia

  • Finite-state machine — State machine redirects here. For infinite state machines, see State transition system. For fault tolerance methodology, see State machine replication. SFSM redirects here. For the Italian railway company, see Circumvesuviana. A finite state… …   Wikipedia

  • State machine replication — Introduction from Schneider s 1990 survey: : Distributed software is often structured in terms of clients and services. Each service comprises one or more servers and exports operations that clients invoke by making requests. Although using a… …   Wikipedia

  • State University of New York at Binghamton — Infobox University name = Binghamton University State University of New York size = 300px motto = From breadth through depth to perspective established = 1946 type = Public Faculty = 551 (full time only) employees = 5,000+ endowment = $68.9… …   Wikipedia

  • State logic — A State logic control system is a programming method created for PLCs.A state logic control system uses a state transition diagram as a model of reality, thus using the fundamentals of finite state machine theory as the basis of a programming… …   Wikipedia

  • State Roads in Florida — infobox state highway system shields= caption=Standard (left) and toll (right) State Road shields state=State Road X (SR X) interstate=Interstate X (I X) us=U.S. Highway X (US X) notes=State Roads are generally state maintained.Roads maintained… …   Wikipedia

  • Abstract rewriting system — In mathematical logic and theoretical computer science, an abstract rewriting system (also (abstract) reduction system or abstract rewrite system; abbreviation ARS) is a formalism that captures the quintessential notion and properties of… …   Wikipedia

Share the article and excerpts

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