最短試験系列を多項式時間で計算可能なプロトコルのクラスについて
スポンサーリンク
概要
- 論文の詳細を見る
通信プロトコルがその仕様通りに実装されているか否かを試験することは実用上極めて重要な問題である.実装されたプロトコルの内部状態を外部から直接識別することはできないので,一般にメッセージの入出力によって内部状態を同定する方法が用いられる.この状態の同定と,状態での入力に対する正しい出力の確認に必要なメッセージ系列をプロトコルの試験系列と言う.試験,のコストを削減するためには試験系列の長さを短くすることが要求される.一般に任意のプロトコルに対して,最短試験系列を多項式時間で求めることはできないと予想されている.本稿では,最短試験系列を多項式時間で計算可能なプロトコルのクラスについて議論し,従来の研究で報告されていたプロトコルのクラスを真に含む,実用的なプロトコルのクラスを新しく提案する.
- 一般社団法人情報処理学会の論文
- 1992-09-28
著者
関連論文
- VANET環境における車両位置情報を用いた蓄積運搬転送による高信頼データ転送方式 (アドホックネットワーク)
- モバイルアドホックネットワークにおける局所的に分割された往復パスを用いたルーチング(変革を続けるネットワークソフトウェア技術論文)
- アドホックネットワーククラスタリングにおける隣接ノード数に基づく適応型電力制御法(ネットワーク,通信の未来を担う学生論文)
- 変革を続けるネットワークソフトウェア技術論文特集の発行にあたって
- ラウンドモデルからの変換による非同期コンセンサスアルゴリズムの導出(ネットワーク環境でのディペンダビリティ)
- 3状態相互排他アルゴリズムの安定時間の下限について
- 非構造化オーバーレイネットワーク構築におけるメトロポリス法を用いたアルゴリズムの評価(ディペンダブルコンピュータシステムとセキュリティ技術及び一般)
- 5 組込みシステムにおけるソフトウェアプロダクトラインの導入(ソフトウェア再利用の新しい波-広がりを見せるプロダクトライン型ソフトウェア開発-)
- データフロー図の階層的作成を支援するシステムの開発
- Analyzerの簡単化 (情報科学の数学的理論)
- 並列論理シミュレーションにおけるロールバックについて
- B-19-15 アプリケーション層によるMANETs向け転送レート調節機構(B-19.ネットワークソフトウェア,一般セッション)
- モデル検査入門
- モデル検査を用いたコンセンサスアルゴリズムの合意性検証(ネットワーク環境でのディペンダビリティ)
- Interpolantを利用したモデル検査による機能競合の検証(ネットワーク環境でのディペンダビリティ)
- 耐故障分散アルゴリズムに対するPROMELAモデルの生成(ディペンダブルコンピューティングシステム及び一般)
- 招待講演 スケーラビリティとアダプタビリティを有するモバイルアドホックネットワーク技術 (アドホックネットワーク)
- B-19-14 モバイルアドホックネットワークにおける適応的クラスタ間データ転送機能を用いた階層マルチキャストルーティング(B-19.ネットワークソフトウェア,一般セッション)
- MANETプロトコルの仕様適合性試験のための状態遷移図縮退手法(ネットワークソフトウェア論文)
- B-19-33 アドホックネットワークを活用した児童見守りシステムにおける誤登録された経路の修復(B-19. ネットワークソフトウェア,一般セッション)
- B-19-32 アドホックネットワークを活用した児童見守りシステムにおける直前のタグ情報を利用した認識率の向上(B-19. ネットワークソフトウェア,一般セッション)
- トポロジ生成機能を備えたアドホックネットワークソフトウェア向け試験環境システムの開発(アドホックネットワーク)
- アドホックネットワークテストベッドにおける端末情報収集機能の開発(アドホックネットワーク)
- アドホックネットワークにおける高信頼通信の性能向上を目指したSCTPの改良と評価(アドホックネットワーク)
- センサネットワークにおける間欠通信のための経路を考慮した同期方式の提案(無線ネットワーク・センサネットワーク,インターネットトラヒック,TCP/IP,性能解析・評価,ネットワークモデル及び一般)
- センサネットワークにおけるデータ集約を効率化するクラスタリング手法(無線ネットワーク・センサネットワーク,インターネットトラヒック,TCP/IP,性能解析・評価,ネットワークモデル及び一般)
- B-21-9 大規模アドホックネットワークにおける階層ルーティングのスケーラビリティに関する評価(B-21.アドホックネットワーク,一般講演)
- B-21-8 モバイルアドホックネットワークにおける局所的パケット再送機能を備えた経路分割ルーテイング方式(B-21.アドホックネットワーク,一般講演)
- B-19-8 キャッシュ機能を用いたアドホックネットワーク画像配信システム(B-19.ネットワークソフトウェア,一般講演)
- ソフトウェアメトリクスのデータマイニングによる障害発生要因特定
- B-19-7 センサネットワークの長寿命化のための省電力通信を用いた経路探索法(B-19.ネットワークソフトウェア,一般セッション)
- 指向性アンテナを有する移動体によって構成されるアドホックネットワークにおける通信制御プロトコル(一般,次世代・新世代ネットワーク,IMS, FMC,フェムトセル,情報家電ネットワーク,シームレス通信,プレゼンス,IPTV, VoD及び一般)
- 非構造化オーバーレイネットワーク構築におけるメトロポリス法を用いたアルゴリズムの評価(ディペンダブルコンピュータシステムとセキュリティ技術及び一般)
- 製品リリース履歴における論理的結合集合に基づいた横断フィーチャ分析法
- メソッド呼び出しに関する不具合修正での変更作業の分析
- ソフトウェアプロジェクト予測に用いるメトリクスの削減
- ベイズ識別器による不具合予測のための相関ルールマイニングを用いたメトリクス絞り込み
- ソフトウェア開発データに対する相関ルールマイニングを利用した不具合増加要因の調査
- ソフトウェアプロジェクト診断のためのチェックリスト導出(レビュー,品質(学生セッション))
- 企業横断的データからのプロジェクト改善案の相関ルールマイニングによる抽出
- B-19-7 アドホック通信を活用した児童見守りシステムの開発(B-19.ネットワークソフトウェア,一般講演)
- 安定的なセンサネットワーク構築のためのマルチパス設定手法(ネットワーク制御,コンテンツ配信,コンテキストアウェアネス,IPv6,認証,ID/名前管理及び一般)
- GPUを用いた状態可到達性解析の高速化(ネットワーク環境でのディペンダビリティ,及び一般)
- 欠損を含むプロジェクトデータからのプロジェクト成否予測のための特徴抽出
- Webアプリケーションの脆弱性検出を目的とした自動テストツールの性能評価(ネットワーク環境でのディペンダビリティ,及び一般)
- メソッドに対するコメント文記述の変更履歴とメソッドの不具合との関係に関する実証的考察 (ソフトウェアサイエンス)
- フォールトプローンモジュール検出手法間の精度比較 : Fault-pronenessフィルタリングとロジスティック回帰
- ソースコード中に含まれる不具合トークンをテキスト分類に基づいて推定するツールの試作と評価
- ソースコード中に含まれる不具合トークンをテキスト分類に基づいて推定するツールの試作と評価
- ピアの近接性を考慮したスキップグラフの構築
- 1-2 スパムフィルタリングに基づくフォールトプローンモジュール検出器の開発(セッション1「プロジェクト管理・ソフト」)
- 再構成可能なリスポンシブシステムのモデリングと性能評価
- 5B-2 品質定量指標のための異なるプログラミング言語間での規模の比較の試み(プロジェクトの定量的管理,一般セッション,ソフトウェア科学・工学,情報処理学会創立50周年記念)
- B-19-7 Androidと自律分散クラスタリングを用いた新世代児童見守りシステムの構築に向けて(B-19.ネットワークソフトウェア,一般セッション)
- 交通密度と平均速度との相関を考慮したVANETにおける渋滞回避走行ルート発見手法(TCP,一般,QoS制御,ネットワーク品質,IPv6,IPバックボーンネットワーク,ディペンダブルネットワーク,ネットワークモデル及び一般)
- C++プログラムに対する複雑さメトリクスの提案と大学環境での実験的評価
- ピアの近接性を考慮したスキップグラフの構築
- ピアの近接性を考慮したスキップグラフの構築
- 5B-1 相関ルールマイニングを利用したソフトウェアプロジェクト混乱要因の関連性に関する調査(プロジェクトの定量的管理,一般セッション,ソフトウェア科学・工学,情報処理学会創立50周年記念)
- 通信プロトコルのリアルタイム性に関する諸性質の検証
- リスポンシブプロトコルのリアルタイム性検証のための時間を考慮した可到達解析法
- B-21-4 MANETにおける自律分散クラスタリングに基づく経路情報の分散管理手法(B-21.アドホックネットワーク,一般セッション)
- B-19-15 MANETのサービス発見手法におけるサービス情報の変化に適応したモバイルエージェントの移動機構(B-19.ネットワークソフトウェア,一般セッション)
- B-21-1 パケット変換とアドレス共有による異種アドホックネットワーク間ルーティング(B-21.アドホックネットワーク,一般セッション)
- リスポンシブシステムについて(信頼性-情報通信システムの性能評価)
- The Third International Workshop on Responsive Computer Systemsの参加報告
- コネクションレスネットワークにおけるフォールトトレラントマルチパスルーティングプロトコルの合成法
- システム特性を考慮したペアワイズテストの改良
- サーベイ論文「ペアワイズテスト-ソフトウェアテストの効率化を求めて-」に関する訂正と補足
- 情報家電システムの安全検証(「信頼性・保全性・安全性の事例:情報処理・ソフトウェア編」〜信頼性ハンドブック出版から10年を経て〜)
- 単一多数決器を用いたカスケード式TMRの最適構成の導出(ディペンダブルコンピューティングシステム及び一般)
- 単一多数決器を用いたカスケード式TMRの最適構成の導出(ディペンダブルコンピューティングシステム及び一般)
- 耐故障分散アルゴリズムに対するPROMELAモデルの生成(ディペンダブルコンピューティングシステム及び一般)
- 大学環境でのオブジェクト指向設計メトリクス適用の試み
- オブジェクト指向開発の設計文書における安全性検証の試み
- C++プログラムの複雑さ評価尺度の定量的評価
- オブジェクト指向設計に関する安全性の検証
- 設計レビューにおけるフォールト検出に関する一考察
- コントロールフローグラフにおける辺のペアを考慮したコードカバレッジの提案と評価 (ソフトウェアサイエンス)
- ソフトウエアプロセス定量化モデルの提案(一般セッション(1))
- ペトリネットによるプログラム開発演習のモデル化とそのモデルによるプログラマ作業効率の定量的評価
- 不具合修正に関わるメソッド呼び出しの変更についての定量的分析
- ソースコードの構造に対する体系的変更内容の復元 (知能ソフトウェア工学)
- ソースコードの構造に対する体系的変更内容の復元 (ソフトウェアサイエンス)
- メソッドに対するコメント文記述の変更履歴とメソッドの不具合との関係に関する実証的考察
- 最短試験系列を多項式時間で計算可能なプロトコルのクラスについて
- 適合性試験において複数フォールトの位置を決定する方法
- 最短試験系列を多項式時間で計算可能なプロトコルのクラスについて
- コントロールフローグラフにおける辺のペアを考慮したコードカバレッジの提案と評価
- ハイブリッドスライスにおけるブレークポイント設定に関する考察
- 欠損率の高いプロジェクトデータを利用したプロジェクトの成否予測
- ソースコードの構造に対する体系的変更内容の復元
- ソースコードの構造に対する体系的変更内容の復元
- 上界のない整数型変数を有する並行システムに対するk帰納法を用いたモデル検査(ネットワーク環境でのディペンダビリティ,及び一般)
- ネットワークコーディングに基づくゴシップの提案(ネットワーク環境でのディペンダビリティ,及び一般)
- 拡張一般化確率ネットに基づくプロジェクトシミュレータにおけるパラメータ設定について
- 開発履歴メトリクスを用いた細粒度なFault-proneモジュール予測
- 開発履歴メトリクスを用いた細粒度なFault-proneモジュール予測
- プログラム開発におけるチーム性能のモデルに基づく実験的評価 : プログラマ性能モデルの拡張
- ソフトウェア信頼度成長モデルの適用技術 (ソフトウェア信頼性モデルの現状と課題)