Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Transition system
Summary
In theoretical computer science, a transition system is a concept used in the study of computation. It is used to describe the potential behavior of discrete systems. It consists of states and transitions between states, which may be labeled with labels chosen from a set; the same label may appear on more than one transition. If the label set is a singleton, the system is essentially unlabeled, and a simpler definition that omits the labels is possible.
Transition systems coincide mathematically with abstract rewriting systems (as explained further in this article) and directed graphs. They differ from finite-state automata in several ways:
The set of states is not necessarily finite, or even countable.
The set of transitions is not necessarily finite, or even countable.
No "start" state or "final" states are given.
Transition systems can be represented as directed graphs.
Formally, a transition system is a pair where is a set of states and , the transition relation, is a subset of . We say that there is a transition from state to state iff , and denote it .
A labelled transition system is a tuple where is a set of states, is a set of labels, and , the labelled transition relation, is a subset of . We say that there is a transition from state to state with label iff and denote it
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. Labelled transitions systems were originally introduced as named transition systems.
If, for any given and , there exists only a single tuple in , then one says that is deterministic (for ).
If, for any given and , there exists at least one tuple in , then one says that is executable (for ).
The formal definition can be rephrased as follows. Labelled state transition systems on with labels from correspond one-to-one with functions , where is the (covariant) powerset functor.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.