ロゴ
ユニオンペディア
コミュニケーション
Google Play で手に入れよう
新しい! あなたのAndroid™デバイスでユニオンペディアをダウンロードしてください!
ダウンロード
ブラウザよりも高速アクセス!
 

状態遷移系

索引 状態遷移系

態遷移系(じょうたいせんいけい、State Transition System)とは、理論計算機科学での計算の研究に使用される抽象機械の一種。状態遷移系は状態群と状態間の遷移から構成される。 状態と遷移が有限個の状態遷移系は有向グラフで表すことができる。 また、状態遷移系は「ラベル付き」と「ラベル無し」の2種類に分類することができる。.

9 関係: 双模倣性二項関係グラフ理論タプル理論計算機科学遷移計算抽象機械操作的意味論

双模倣性

双模倣性(そうもほうせい、Bisimulation)とは、理論計算機科学における複数の状態遷移系の間の同値関係を意味する。そのようなシステムは、互いに他のシステムの動作をシミュレートできるという意味で同じ動作が可能である。 直感的に言えば、同じ動作をする2つのシステムは「双模倣的」である。その意味で観察者から見て両システムは区別できない。 クリプキモデルは(ラベル付き)状態遷移系の特殊ケースであるため、双模倣性は様相論理学の概念とも言える。.

新しい!!: 状態遷移系と双模倣性 · 続きを見る »

二項関係

数学において、二項関係(にこうかんけい、binary relation)あるいは二変数関係 (dyadic relation, 2-place relation) は、集合 の元からなる順序対のあつまりである。別な言い方をすれば、直積集合 の部分集合を、集合 上の二項関係と呼ぶ。あるいはもっと一般に、二つの集合 に対して、 と との間の二項関係とは、直積 の部分集合のことをいう。 二項関係の一つの例は素数全体の成す集合 と整数全体の成す集合 の間の整除関係である。この整除関係では任意の素数 は、 の倍数である任意の整数 に関係を持ち、倍数でない整数には関係しないものとして扱われる。例えば、素数 が関係を持つ整数には などが含まれるが や は含まれない。同様に素数 が関係する整数として などが挙げられるが、 や はそうではない。 二項関係は数学のさまざまな分野で用いられ、不等関係、恒等関係、算術の整除関係、初等幾何学の合同関係、グラフ理論の隣接関係、線型代数学の直交関係などのさまざまな概念が二項関係として定式化することができる。また、写像の概念を特別な種類の二項関係として定義することもできる。二項関係は計算機科学においても重用される。 二項関係はn-項関係 (各 -番目の成分が関係の -番目の始集合 からとられているようなn-組からなる集合)で とした特別の場合である。 ある種の公理的集合論では(集合の一般化としての)類の上の関係を考えることができる。このような拡張は、集合論における元の帰属関係や包含関係の概念(に限った話ではないが)のモデル化を、ラッセルの逆理のような論理矛盾に陥らずに行うために必要である。.

新しい!!: 状態遷移系と二項関係 · 続きを見る »

グラフ理論

ラフ理論(グラフりろん、graph theory)は、ノード(節点・頂点)の集合とエッジ(枝・辺)の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。.

新しい!!: 状態遷移系とグラフ理論 · 続きを見る »

タプル

タプルまたはチュープル(tuple)とは、複数の構成要素からなる組を総称する一般概念。 数学や計算機科学などでは通常、順序付けられた対象の並びを表すために用いられる。個別的には、n 個でできた組を英語で「n-tuple」と書き、日本語に訳す場合は通常「n 組」としている。タプルの概念そのものも組と呼ばれる場合がある。なお、 n-tuple は数学のタプルを意味するほか、同様に double、triple などの拡張として倍数詞の表現にも利用される(詳細は「倍#西洋数学における n 倍を表す表現」を参照)。.

新しい!!: 状態遷移系とタプル · 続きを見る »

理論計算機科学

論計算機科学(りろんけいさんきかがく、英語:theoretical computer science)は計算機を理論的に研究する学問で、計算機科学の一分野である。計算機を数理モデル化して数学的に研究することを特徴としている。「数学的」という言葉は広義には公理的に扱えるもの全てを指すので、理論計算機科学は広義の数学の一分野でもある。理論計算機科学では、現実のコンピュータを扱うことも多いが、チューリングマシンなどの計算モデルを扱うことも多い。 理論計算機科学の代表的な分野として以下のものがある。.

新しい!!: 状態遷移系と理論計算機科学 · 続きを見る »

遷移

遷移(せんい)とは、「うつりかわり」のこと。類義語として「変遷」「推移」などがある。 自然科学の分野では transition の訳語であり、一般に、何らかの事象(物)が、ある状態から別の状態へ変化すること。さまざまな分野で使われており、場合によって意味が異なることもある。以下に解説する。.

新しい!!: 状態遷移系と遷移 · 続きを見る »

計算

計算(けいさん)とは、与えられた情報をもとに、命題に従って演繹することである。 これは人間が無意識のレベルで行っている判断(→判断力)や、動物一般が行っている思考を、計算という形で意識化する手法ともいえ、その意味では「ものを考えること」一般が「計算」の一種だとみなすことも可能である。計算に使用される手続きはアルゴリズムと呼ばれる。対人関係において、戦略をアルゴリズムとして状況を有利に運ぶことも時に「計算」と表現される。 もっとも一般的かつ義務教育の範疇で最初に習うものは、算術(算数)における四則演算を、演算記号に示されたアルゴリズム通りに処理するものである。こういった「計算」は日常生活から専門的分野まで幅広く行われており、これを専門に処理する装置や機械も、人類の歴史において数多く開発され利用されている。.

新しい!!: 状態遷移系と計算 · 続きを見る »

抽象機械

抽象機械(抽象コンピュータとも呼ばれる)は、オートマトンで利用される、コンピュータハードウェアやソフトウェアシステムの理論上モデルである。 計算処理の抽象化は、計算機科学と計算機工学の両方の分野で行われ、通常は離散時間パラダイムを仮定している。.

新しい!!: 状態遷移系と抽象機械 · 続きを見る »

操作的意味論

操作的意味論(そうさてきいみろん、Operational Semantics)とは、プログラムの意味を数学的に厳密に与える計算機科学の手法の一種(プログラム意味論参照)。.

新しい!!: 状態遷移系と操作的意味論 · 続きを見る »

出ていきます入ってきます
ヘイ!私たちは今、Facebook上です! »