Transition system (original) (raw)
Přechodový systém je v teoretické informatice používaný pro studium výpočtů a chování procesů. Stroj sestává z množiny stavů a z přechodů mezi stavy. Přechodové systémy se dělí na „označené“ (labelled) a „neoznačené“ (unlabelled).
| Property | Value |
|---|---|
| dbo:abstract | Přechodový systém je v teoretické informatice používaný pro studium výpočtů a chování procesů. Stroj sestává z množiny stavů a z přechodů mezi stavy. Přechodové systémy se dělí na „označené“ (labelled) a „neoznačené“ (unlabelled). (cs) يعرّف نظام حالة انتقال في المعلوماتية النظرية على أنه آلة افتراضية تستخدم في الاحتساب. تحتوي هذه الآلة على مجموعة من الحالات والانتقالات بين هذه الحالات، من الممكن تعريف مجموعة من العناوين وعنونة الانتقالات بها، من الممكن أن يستخدم العنوان لأكثر من انتقال واحد. لا يتم عنونة النظام في حال احتوت مجموعة العناوين على عنصر واحد فقط، ومن الممكن استخدام تعريف بسيط للنظام يتم به حذف العناوين. تتطابق أنظمة حالة انتقال رياضيات مع أنظمة إعادة الكتابة المجردة. بالمقابل فهي تختلف عن أوتومات الحالة المنتهية بعدة أمور: * ليس من الضروري أن تكون مجموعة الحالات منتهيةً، أو حتى قابلةً للعد في أنظمة حالة-انتقال. * ليس من الضروري أن تكون مجموعة الانتقالات منتهيةً، أو حتى قابلةً للعد في أنظمة حالة-انتقال. * في أوتومات الحالة المنتهية يتم التمييز بين حالة «بداية» وحيدة، ومجموعة من حالات «النهاية». من الممكن تمثيل نظام حالة-انتقال كـبيان موجه. (ar) Ein Transitionssystem (englisch transition system) beschreibt in der Automatentheorie die möglichen Zustände eines zustandsbasierten Systems und die möglichen Übergänge (Transitionen) zwischen diesen Zuständen. Man unterscheidet dabei diskrete und kontinuierliche Systeme. In der Regel betrachtet man nur diskrete Systeme, da diese wesentlich leichter überprüft werden können. Ferner unterscheidet man deterministische und nichtdeterministische Transitionssysteme. Im ersten Fall wird einem Zustand und einer Transition höchstens ein Folgezustand zugeordnet, während im nichtdeterministischen Fall derselbe Zustand zu einer Transition mehrere Nachfolgezustände besitzen kann. Deterministische Transitionssysteme sind in diesem Sinne Spezialfälle von nichtdeterministischen Transitionssystemen. Ein Transitionssystem kann verwendet werden, um bestimmte Eigenschaften eines zustandsbasierten Systems zu zeigen, insbesondere die Terminiertheit. Aus diesem Grund wird es zur Verifikation der Korrektheit von Algorithmen eingesetzt. Auch zum Beweis der Verklemmungsfreiheit von verteilten Systemen kann dieses Konstrukt angewendet werden. (de) En informatique théorique, un système de transition d'états est une forme de machine abstraite utilisée pour modéliser un ou des calcul(s). Un système de transition d'états est constitué d'un ensemble d'états et d'un ensemble de transitions d'un état à un autre, qui peuvent être étiquetées ; une même étiquette peut apparaître sur plusieurs transitions. Si l'ensemble des étiquettes est un singleton, on peut omettre l'étiquetage. Les systèmes d'états-transitions sont des graphes orientés. (fr) In informatica teorica un sistema a transizione di stati è una macchina astratta usata nella teoria della computazione. In letteratura viene indicato con LTS dal nome inglese Labelled Transition System. La macchina consiste di un insieme di stati e transizioni tra gli stati, che possono essere etichettate con etichette scelte da un insieme; la stessa etichetta può apparire su più di una transizione. Se l'insieme delle etichette è composto da un solo elemento, il sistema è essenzialmente privo di etichette, e una definizione più semplice che omette le etichette è possibile. I sistemi a transizione di stati differiscono comunque dagli automi a stati finiti in più modi: * In un sistema a transizione di stati l'insieme di stati non è necessariamente finito o numerabile. * In un sistema a transizione di stati l'insieme delle transizioni non è necessariamente finito o numerabile. I sistemi a transizione di stati possono essere rappresentati come grafi orientati. (it) 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. (en) 状態遷移系（じょうたいせんいけい、State Transition System）とは、理論計算機科学での計算の研究に使用される抽象機械の一種。状態遷移系は状態群と状態間の遷移から構成される。 状態と遷移が有限個の状態遷移系は有向グラフで表すことができる。 また、状態遷移系は「ラベル付き」と「ラベル無し」の2種類に分類することができる。 (ja) Na teoria da ciência da computação, um sistema de transição é um conceito utilizado no estudo da computação. É usado para descrever o comportamento potencial de sistemas discretos. Consiste de estados e transições entre estados, que podem ser rotuladas com etiquetas escolhidas a partir de um conjunto; o mesmo rótulo pode aparecer em mais de uma transição. Se o conjunto de rótulos é um conjunto unitário, o sistema é essencialmente sem rótulo, e uma definição mais simples que omite os rótulos é possível. Sistemas de transição coincidem matematicamente com sistemas de reescrita abstratos (como explicado mais adiante neste artigo) e grafos direcionados. Eles diferem de autômatos finitos em várias maneiras: * O conjunto de estados não é necessariamente finito, ou mesmo contável. * O conjunto de transições não é necessariamente finito, ou mesmo contável. * Nenhum estado "inicio" ou estado "final" são dadas. Sistemas de transição podem ser representados como grafos direcionados. (pt) 在计算机科学和控制理论中，“变迁系统”用数学的方法描述离散系统的行为。变迁系统主要由“状态”和状态之间的“状态迁移”组成。有标号的变迁系统可以从已定义的标签集合中选择相应标签来标记状态迁移，而且相同的标签可能被应用在多个状态迁移上。变迁系统也可以是无标记的，此时也可以认为标签集合中只有单一标签元素，从而省略了状态迁移上的标签记号。 变迁系统在数学定义上和有向图一致，但与有限状态自动机有一定不同。 变迁系统的特点有： * 系统状态的集合不一定是有限的或可数的； * 状态迁移的集合不一定是有限的或可数的； * 变迁系统并不需要给出“开始”状态或“最终”状态； * 变迁系统可以表示为有向图，有限状态自动机则不能。 (zh) Модель станів і переходів — абстрактний автомат, використовується для дослідження обчислень. Модель складається із множини станів та переходів між станами. Моделі станів та переходів мають декілька відмінностей від скінченних автоматів: * Моделі станів і переходів мають не обов'язково скінченну або зліченну кількість станів * Моделі станів і переходів мають не обов'язково скінченну або зліченну множину переходів Моделі станів і переходів із скінченною кількістю станів та переходів можна представити у вигляді орієнтованих графів. Існує щонайменше два типи моделей станів і переходів: марковані та немарковані. (uk) |
| dbo:wikiPageID | 10768144 (xsd:integer) |
| dbo:wikiPageLength | 5944 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1094599884 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Power_set dbr:Semigroup_action dbr:Model_checking dbr:Operational_semantics dbr:Simulation_preorder dbr:Computation dbr:State_(computer_science) dbr:Theoretical_computer_science dbr:Action_language dbr:Transformation_monoid dbr:Transition_monoid dbr:Finite-state_automata dbr:Directed_graph dbr:Discrete_system dbr:Abstract_rewriting_system dbc:Models_of_computation dbr:Bijection dbr:Bisimulation dbr:Automata_theory dbr:Modal_μ-calculus dbr:Singleton_(mathematics) dbr:F-coalgebra dbr:Finite-state_machine dbr:Kripke_structure |
| dbp:wikiPageUsesTemplate | dbt:About dbt:Authority_control dbt:Reflist |
| dct:subject | dbc:Models_of_computation |
| gold:hypernym | dbr:Concept |
| rdf:type | owl:Thing yago:WikicatModelsOfComputation yago:Assistant109815790 yago:CausalAgent100007347 yago:LivingThing100004258 yago:Model110324560 yago:Object100002684 yago:Organism100004475 yago:Person100007846 yago:PhysicalEntity100001930 yago:Worker109632518 yago:YagoLegalActor yago:YagoLegalActorGeo yago:Whole100003553 |
| rdfs:comment | Přechodový systém je v teoretické informatice používaný pro studium výpočtů a chování procesů. Stroj sestává z množiny stavů a z přechodů mezi stavy. Přechodové systémy se dělí na „označené“ (labelled) a „neoznačené“ (unlabelled). (cs) En informatique théorique, un système de transition d'états est une forme de machine abstraite utilisée pour modéliser un ou des calcul(s). Un système de transition d'états est constitué d'un ensemble d'états et d'un ensemble de transitions d'un état à un autre, qui peuvent être étiquetées ; une même étiquette peut apparaître sur plusieurs transitions. Si l'ensemble des étiquettes est un singleton, on peut omettre l'étiquetage. Les systèmes d'états-transitions sont des graphes orientés. (fr) 状態遷移系（じょうたいせんいけい、State Transition System）とは、理論計算機科学での計算の研究に使用される抽象機械の一種。状態遷移系は状態群と状態間の遷移から構成される。 状態と遷移が有限個の状態遷移系は有向グラフで表すことができる。 また、状態遷移系は「ラベル付き」と「ラベル無し」の2種類に分類することができる。 (ja) 在计算机科学和控制理论中，“变迁系统”用数学的方法描述离散系统的行为。变迁系统主要由“状态”和状态之间的“状态迁移”组成。有标号的变迁系统可以从已定义的标签集合中选择相应标签来标记状态迁移，而且相同的标签可能被应用在多个状态迁移上。变迁系统也可以是无标记的，此时也可以认为标签集合中只有单一标签元素，从而省略了状态迁移上的标签记号。 变迁系统在数学定义上和有向图一致，但与有限状态自动机有一定不同。 变迁系统的特点有： * 系统状态的集合不一定是有限的或可数的； * 状态迁移的集合不一定是有限的或可数的； * 变迁系统并不需要给出“开始”状态或“最终”状态； * 变迁系统可以表示为有向图，有限状态自动机则不能。 (zh) يعرّف نظام حالة انتقال في المعلوماتية النظرية على أنه آلة افتراضية تستخدم في الاحتساب. تحتوي هذه الآلة على مجموعة من الحالات والانتقالات بين هذه الحالات، من الممكن تعريف مجموعة من العناوين وعنونة الانتقالات بها، من الممكن أن يستخدم العنوان لأكثر من انتقال واحد. لا يتم عنونة النظام في حال احتوت مجموعة العناوين على عنصر واحد فقط، ومن الممكن استخدام تعريف بسيط للنظام يتم به حذف العناوين. تتطابق أنظمة حالة انتقال رياضيات مع أنظمة إعادة الكتابة المجردة. بالمقابل فهي تختلف عن أوتومات الحالة المنتهية بعدة أمور: من الممكن تمثيل نظام حالة-انتقال كـبيان موجه. (ar) Ein Transitionssystem (englisch transition system) beschreibt in der Automatentheorie die möglichen Zustände eines zustandsbasierten Systems und die möglichen Übergänge (Transitionen) zwischen diesen Zuständen. Man unterscheidet dabei diskrete und kontinuierliche Systeme. In der Regel betrachtet man nur diskrete Systeme, da diese wesentlich leichter überprüft werden können. (de) 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 can be represented as directed graphs. (en) In informatica teorica un sistema a transizione di stati è una macchina astratta usata nella teoria della computazione. In letteratura viene indicato con LTS dal nome inglese Labelled Transition System. La macchina consiste di un insieme di stati e transizioni tra gli stati, che possono essere etichettate con etichette scelte da un insieme; la stessa etichetta può apparire su più di una transizione. Se l'insieme delle etichette è composto da un solo elemento, il sistema è essenzialmente privo di etichette, e una definizione più semplice che omette le etichette è possibile. (it) Na teoria da ciência da computação, um sistema de transição é um conceito utilizado no estudo da computação. É usado para descrever o comportamento potencial de sistemas discretos. Consiste de estados e transições entre estados, que podem ser rotuladas com etiquetas escolhidas a partir de um conjunto; o mesmo rótulo pode aparecer em mais de uma transição. Se o conjunto de rótulos é um conjunto unitário, o sistema é essencialmente sem rótulo, e uma definição mais simples que omite os rótulos é possível. Sistemas de transição podem ser representados como grafos direcionados. (pt) Модель станів і переходів — абстрактний автомат, використовується для дослідження обчислень. Модель складається із множини станів та переходів між станами. Моделі станів та переходів мають декілька відмінностей від скінченних автоматів: * Моделі станів і переходів мають не обов'язково скінченну або зліченну кількість станів * Моделі станів і переходів мають не обов'язково скінченну або зліченну множину переходів Моделі станів і переходів із скінченною кількістю станів та переходів можна представити у вигляді орієнтованих графів. (uk) |
| rdfs:label | نظام حالة الانتقال (ar) Přechodový systém (cs) Transitionssystem (de) Système de transition d'états (fr) Sistema a transizione di stati (it) 状態遷移系 (ja) Sistema de Transição (pt) Transition system (en) Модель станів і переходів (uk) 变迁系统 (zh) |
| owl:sameAs | freebase:Transition system yago-res:Transition system http://d-nb.info/gnd/4329099-1 wikidata:Transition system dbpedia-ar:Transition system dbpedia-cs:Transition system dbpedia-de:Transition system dbpedia-fr:Transition system dbpedia-it:Transition system dbpedia-ja:Transition system dbpedia-pt:Transition system dbpedia-tr:Transition system dbpedia-uk:Transition system dbpedia-zh:Transition system https://global.dbpedia.org/id/iPqi |
| prov:wasDerivedFrom | wikipedia-en:Transition_system?oldid=1094599884&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Transition_system |
| is dbo:wikiPageDisambiguates of | dbr:Transition |
| is dbo:wikiPageRedirects of | dbr:State_transition_system dbr:Labeled_Transition_System dbr:Labeled_transition_system dbr:Labelled_transition_system |
| is dbo:wikiPageWikiLink of | dbr:Principles_of_Model_Checking dbr:Deterministic_finite_automaton dbr:Glossary_of_artificial_intelligence dbr:Monoid dbr:Theory_of_regions dbr:Logic dbr:Computation_tree_logic dbr:Averest dbr:Frame_problem dbr:Bisimulation dbr:Hidden_algebra dbr:Transition dbr:Widening_(computer_science) dbr:Kripke_structure_(model_checking) dbr:Well-structured_transition_system dbr:F-coalgebra dbr:LTSA dbr:Finite-state_machine dbr:Post's_theorem dbr:Stutter_bisimulation dbr:Systems_immunology dbr:State_transition_system dbr:Labeled_Transition_System dbr:Labeled_transition_system dbr:Labelled_transition_system |
| is foaf:primaryTopic of | wikipedia-en:Transition_system |