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

モデル検査

索引 モデル検査

モデル検査(Model Checking)とは、形式システムをアルゴリズム的に検証する手法である。ハードウェアやソフトウェアの設計から導出されたモデルが形式仕様を満足するかどうか検証する。仕様は時相論理の論理式の形式で記述することが多い。.

30 関係: Association for Computing Machinery健全性二分決定図仕様形式的検証ミューテックスハードウェアハードウェア記述言語ブーリアン型制御構造アルゴリズムアレン・エマーソンエドムンド・クラークグラフ理論ゲーム意味論システムソフトウェア充足可能性問題BLAST組合せ爆発静的コード解析計算木論理自動定理証明SPINモデルチェッカ抽象解釈有限オートマトン時相論理1986年1999年2004年

Association for Computing Machinery

Association for Computing Machinery (ACM) は、ニューヨークに本部のあるコンピュータ科学分野の国際学会。1947年設立。IEEEとともに、この分野で最も影響力の強い学会であり、IEEEがその名と由来や歴史からエレクトロニクスや通信分野の工学に強いのに対し、数学的な理論計算機科学のような分野もカバーする。日本語に訳して「計算機械学会」とされることもあるが、こんにちこの訳語が用いられることはほとんどなく、通常は単に"ACM"という略称で呼ばれるのがもっぱらである。ACMの「A」は Association (学会、団体) の頭文字であるが、アメリカ数学会 (AMS) と混同して「米国計算機学会」と誤訳されることがある。 数多くの国際会議を開催しており、人目を惹くデモ映像のSIGGRAPHやSIGMODなどはよく知られている。他の多くの学会と同様にすぐれた業績などへの表彰もおこなっているが、チューリング賞は、特にこの分野の最高の賞とみなされており、物理や化学といった分野におけるノーベル賞に匹敵するものと扱われることもある(他の賞についても時折「~のノーベル賞」といったような表現が使われることがあるが、この分野の全てを対象とした世界トップクラスの賞という位置づけにあるのはチューリング賞をおいて他にない)。.

新しい!!: モデル検査とAssociation for Computing Machinery · 続きを見る »

健全性

健全性(けんぜんせい、Soundness)は、論証が次の属性を持つことと同値である。.

新しい!!: モデル検査と健全性 · 続きを見る »

二分決定図

二分決定図(にぶんけっていず、Binary Decision Diagram、BDD)とは、ブール関数を表現するのに使われるデータ構造である。二分決定グラフあるいは(基本的には二分木のような構造であることから)二分決定木と呼ぶこともある。.

新しい!!: モデル検査と二分決定図 · 続きを見る »

仕様

仕様(しよう、英: specification スペシフィケーション)とは、材料・製品・サービスなどが明確に満たさなければならない要求事項の集まりである。日常的には英語を短縮して「スペック」とも。.

新しい!!: モデル検査と仕様 · 続きを見る »

形式的検証

形式的検証(けいしきてきけんしょう)とは、ハードウェアおよびソフトウェアのシステムにおいて形式手法や数学を利用し、何らかの形式仕様記述やプロパティに照らしてシステムが正しいことを証明したり、逆に正しくないことを証明することである。.

新しい!!: モデル検査と形式的検証 · 続きを見る »

ミューテックス

ミューテックス (Mutex) とは、コンピュータプログラミングにおける技術用語。クリティカルセクションでアトミック性を確保するための排他制御や同期機構の一種である。Mutexという語はMUTual EXclusion (相互排他、排他制御) の省略形である。ここでは、狭義の排他制御について述べる。.

新しい!!: モデル検査とミューテックス · 続きを見る »

ハードウェア

ハードウェア (hardware) とは、システムの物理的な構成要素を指す一般用語である。日本語では機械、装置、設備のことを指す。ソフトウェアとの対比語であり、単に「ハード」とも呼ばれる。.

新しい!!: モデル検査とハードウェア · 続きを見る »

ハードウェア記述言語

ハードウェア記述言語(ハードウェアきじゅつげんご、hardware description language、HDL)は、デジタル回路、特に集積回路を設計するためのコンピュータ言語ないしドメイン固有言語(DSL)である。回路の設計、構成を記述する。処理を検証するための試験(テストベンチ)記述ができ、シミュレーションできる開発環境もある。 プログラミング言語との類似性が見られる機能がある言語もあることから、プログラミング言語の一種などとする誤解が非常に多いが、間違いである。また、プログラマブルロジックコントローラの記述に用いられるラダー言語は別のものと扱われている。.

新しい!!: モデル検査とハードウェア記述言語 · 続きを見る »

ブーリアン型

ブーリアン型(ブーリアンがた、Boolean datatype)は、真理値の「真.

新しい!!: モデル検査とブーリアン型 · 続きを見る »

制御構造

制御構造(せいぎょこうぞう)は、コンピュータ・プログラミング言語、特に手続き型プログラミングや命令型プログラミングにおいて、ループや飛び越しなどといった、手続き(プロシージャ)中の実行順を順次実行から変化させたり、サブルーチン呼出しやその戻り、などといった制御を行う「文 (プログラミング) 」などの構造(言語の構成要素)である。 制御構造の種類は言語によって様々だが、典型的には以下のようなものがある(用語「ブロック」については、ブロック (プログラミング) の記事を参照)。.

新しい!!: モデル検査と制御構造 · 続きを見る »

アルゴリズム

フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム(algorithm )とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.

新しい!!: モデル検査とアルゴリズム · 続きを見る »

アレン・エマーソン

アーネスト・アレン・エマーソン(Ernest Allen Emerson、1954年6月2日 - )は、アメリカ合衆国の計算機科学者であり、テキサス大学オースティン校の教授。 エドムンド・クラーク、ジョセフ・シファキスと共にモデル検査の先駆的研究で2007年のチューリング賞を受賞した。1998年には、記号的モデル検査 (Symbolic Model Cheking) の研究に対してACMのパリス・カネラキス実践的理論賞を受賞した。 1976年、テキサス大学オースティン校で数学の学士号を取得し、1981年、ハーバード大学で応用数学の博士号を取得した。 1980年代にエドムンド・クラークと共同研究し、計算木論理を考案した。 ACMの会員である。.

新しい!!: モデル検査とアレン・エマーソン · 続きを見る »

エドムンド・クラーク

ドムンド・クラーク エドムンド・メルソン・クラーク・ジュニア(Edmund Melson Clarke, Jr.、1945年7月27日 - )は、ハードウェアやソフトウェアの設計を形式的に検証するモデル検査の開発で知られている計算機科学者。カーネギーメロン大学計算機科学科の教授。アレン・エマーソン、ジョセフ・シファキスと共に、2007年のACMチューリング賞を受賞。.

新しい!!: モデル検査とエドムンド・クラーク · 続きを見る »

グラフ理論

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

新しい!!: モデル検査とグラフ理論 · 続きを見る »

ゲーム意味論

ーム意味論(ゲームいみろん、Game Semantics)とは、ゲーム理論的概念(プレイヤーの勝利戦略の存在など)に基づいた論理の意味論の手法である。1950年代後半にパウル・ローレンツェンが提唱した。その後、様々なゲーム意味論が研究されてきた。ゲーム意味論はプログラミング言語の形式意味論にも適用されてきた。.

新しい!!: モデル検査とゲーム意味論 · 続きを見る »

システム

テム(system)は、相互に影響を及ぼしあう要素から構成される、まとまりや仕組みの全体。一般性の高い概念であるため、文脈に応じて系、体系、制度、方式、機構、組織といった多種の言葉に該当する。系 (自然科学) の記事も参照。 それ自身がシステムでありながら同時に他のシステムの一部でもあるようなものをサブシステムという。.

新しい!!: モデル検査とシステム · 続きを見る »

ソフトウェア

フトウェア(software)は、コンピューター分野でハードウェア(物理的な機械)と対比される用語で、何らかの処理を行うコンピュータ・プログラムや、更には関連する文書などを指す。ソフトウェアは、一般的にはワープロソフトなど特定の作業や業務を目的としたアプリケーションソフトウェア(応用ソフトウェア、アプリ)と、ハードウェアの管理や基本的な処理をアプリケーションソフトウェアやユーザーに提供するオペレーティングシステム (OS) などのシステムソフトウェアに分類される。.

新しい!!: モデル検査とソフトウェア · 続きを見る »

充足可能性問題

充足可能性問題(じゅうそくかのうせいもんだい、satisfiability problem, SAT)は、一つの命題論理式が与えられたとき、それに含まれる変数の値を偽 (False) あるいは真 (True) にうまく定めることによって全体の値を'真'にできるか、という問題をいう。SATisfiabilityの頭3文字を取ってしばしば「SAT」と呼ばれる。.

新しい!!: モデル検査と充足可能性問題 · 続きを見る »

BLAST

BLAST (Basic Local Alignment Search Tool) は、バイオインフォマティクスでDNAの塩基配列あるいはタンパク質のアミノ酸配列のシーケンスアライメントを行うためのアルゴリズムをいい、またそのアルゴリズムを実装したプログラムをいう。 BLAST を使って、手元にあるシーケンスで、シーケンスデータベースもしくはライブラリに対して検索することにより、ある閾値以上のスコアで類似するシーケンス群を発見することができる。 BLAST は、バイオインフォマティクスで最も広く使われているプログラムの一つである。.

新しい!!: モデル検査とBLAST · 続きを見る »

組合せ爆発

組合せ爆発(くみあわせばくはつ、Combinatorial explosion)は、計算機科学、応用数学、情報工学、人工知能などの分野では、解が組合せ(combination)的な条件で定義される離散最適化問題で、問題の大きさn に対して解の数が指数関数や階乗などのオーダーで急激に大きくなってしまうために、有限時間で解あるいは最適解を発見することが困難になることをいう。.

新しい!!: モデル検査と組合せ爆発 · 続きを見る »

静的コード解析

静的コード解析 (static code analysis) または静的プログラム解析 (static program analysis)とは、コンピュータのソフトウェアの解析手法の一種であり、実行ファイルを実行することなく解析を行うこと。逆にソフトウェアを実行して行う解析を動的プログラム解析と呼ぶ。静的コード解析はソースコードに対して行われることが多く、少数ながらオブジェクトコードに対して行う場合もある。また、この用語は以下に列挙するツールを使用した解析を意味することが多い。人間が行う作業はインスペクション、コードレビューなどと呼ぶ。.

新しい!!: モデル検査と静的コード解析 · 続きを見る »

計算木論理

計算木論理(けいさんきろんり、Computational Tree Logic、CTL)は、分岐時相論理の一種である。その時間モデルでは未来は決定されておらず木構造のように分岐している。未来の複数の経路のうちの1つが実際に現実の経路となる。.

新しい!!: モデル検査と計算木論理 · 続きを見る »

自動定理証明

アルゴンヌ国立研究所は1960年代以降2000年代まで、自動定理証明のリーダーだった。 自動定理証明(automated theorem proving, ATP)とは、自動推論 (AR) の中でも最も成功している分野であり、コンピュータプログラムによって数学的定理に対する証明を発見すること。ベースとなる論理によって、定理の妥当性を決定する問題は簡単なものから不可能なものまで様々である。.

新しい!!: モデル検査と自動定理証明 · 続きを見る »

SPINモデルチェッカ

SPINモデルチェッカ(英: SPIN model checker)は、ソフトウェアのモデル検査のためのツールである。Gerard J. Holzmann らが開発し、15年以上に渡って改良を続けてきた。2001年にAssociation for Computing Machinery (ACM) のソフトウェアシステム賞を受賞している。1995年以来、ほぼ毎年モデル検査に興味のある SPIN ユーザーや研究者による SPIN ワークショップが開催されている。.

新しい!!: モデル検査とSPINモデルチェッカ · 続きを見る »

抽象解釈

抽象解釈(ちゅうしょうかいしゃく、Abstract interpretation)は、コンピュータプログラムの意味論の健全な近似の理論であり、順序集合(特に束)における単調関数に基づいている。全ての計算を実施することなく、プログラムの部分的な実行(ある種の部分評価)をするものと見ることができ、それによりプログラムの意味に関する情報(例えば、制御構造、情報の流れなど)を獲得する。 主な応用として、形式的な静的コード解析があり、プログラム実行に関する情報を自動抽出するものである。このような解析には次の2つの利用法がある。.

新しい!!: モデル検査と抽象解釈 · 続きを見る »

有限オートマトン

有限オートマトン(finite automaton)または有限状態機械(finite state machine, FSM)とは、有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である。デジタル回路やプログラムの設計で使われることがあり、ある一連の状態をとったときどのように論理が流れるかを調べることができる。有限個の「状態」のうち1つの状態をとる。ある時点では1つの状態しかとらず、それをその時点の「現在状態」と呼ぶ。何らかのイベントや条件によってある状態から別の状態へと移行し、それを「遷移」と呼ぶ。それぞれの現在状態から遷移しうる状態と、遷移のきっかけとなる条件を列挙することで定義される。 有限オートマトンは様々な問題に応用でき、半導体設計の自動化、通信プロトコル設計、構文解析などの工学面での応用がある。生物学や人工知能研究では状態機械(群)を使って神経系をモデル化し、言語学では自然言語の文法をモデル化したりする。.

新しい!!: モデル検査と有限オートマトン · 続きを見る »

時相論理

時相論理(Temporal Logic)とは、時間との関連で問題を理解し表現するための規則と表記法の体系である。時相論理では、「私はいつも腹ペコだ」、「私はそのうち腹ペコになる」、「私は何かを食べるまで腹ペコだろう」といった文を表現できる。1950年代末にが提唱した様相論理に基づいた時相論理を特に時制論理(Tense Logic)と呼ぶことがある。が重要な業績を残した。その後、そこから発展し、アミール・プヌーリら計算機科学者や論理学者が研究を進めた。 時相論理はシステムのハードウェアやソフトウェアの要求仕様を記述する方法として形式的検証で利用される。例えば、「要求が発生したら常にリソースへのアクセスがそのうちに承認される。ただし、決して2つの要求を同時に承認してはならない」といった文章は時相論理で表せる。.

新しい!!: モデル検査と時相論理 · 続きを見る »

1986年

この項目では、国際的な視点に基づいた1986年について記載する。.

新しい!!: モデル検査と1986年 · 続きを見る »

1999年

1990年代最後の年であり、1000の位が1になる最後の年でもある。 この項目では、国際的な視点に基づいた1999年について記載する。.

新しい!!: モデル検査と1999年 · 続きを見る »

2004年

この項目では、国際的な視点に基づいた2004年について記載する。.

新しい!!: モデル検査と2004年 · 続きを見る »

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