State transition system
theoretical computer science, a state transition system is an abstract machineused in the study of computation. The machine consists of a set of states and transitions between states.
State transition systems differ from
finite state automatain 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
There are at least two basic types of state transition systems: labelled (or LTS for "labelled transition system") or unlabelled.
Formally, an unlabelled state transition system is a tuple ("S", →) where "S" is a set (of states) and → ⊆ "S" × "S" is a
binary relationover "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
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.
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
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
transition — tran‧si‧tion [trænˈzɪʆn, ˈsɪ ] noun [countable, uncountable] formal the act or process of changing from one state or form to another: • The computer company went through a difficult transition period. • Three directors are expected to retire… … Financial and business terms
State socialism — State socialism, broadly speaking, is any variety of socialism which relies on control of the means of production by the state, either through state ownership or regulation. [cite web url=https://lra.le.ac.uk/handle/2381/3186 title=Leicester… … Wikipedia