プレスブルガー算術を用いたInfeasible Pathの検出
スポンサーリンク
概要
- 論文の詳細を見る
本論文では, 実行不可能経路(IFP)検出の際に用いられる, 存在記号のみにより束縛された冠頭標準形のプレスブルガー文(EPP文)の真偽判定を, 効率良く行う手法を提案する. IFPを検出することにより, 計算経路に沿ったさまざまなプログラム解析を精密に行うことが包括的に可能となる. 一般のプレスブルガー文に対する従来の真偽判定法では, 計算量のオーダが極めて大きく実用的な時間内にIFPが検出できない場合があった. 提案手法では, 従来の判定法において, 変数の係数を表す行列(係数行列)を数論の定理を用いて三角化する. そして, 三角化した係数行列の階数が行列の次数より低い場合, 多元1次不定方程式の解法を用いて係数行列を三角化する. 更に, 後退代入により, EPP文の真偽を判定する. 提案手法では, EPP文における変数の係数の絶対値が大きくなる場合, すなわち, IFP検出における経路条件の係数の絶対値が大きくなる場合, 特に有効である. このような場合, プロトタイプシステムを用いた実験により, 従来手法に比べて最大300万倍の速度向上を確認している.
- 社団法人電子情報通信学会の論文
- 1997-03-25
著者
関連論文
- インターネットQoSビジュアライザのための実時間データ処理システムの構成
- インターネットQoSビジュアライザを用いた遅延とジッターの測定
- インターネットQoSビジュアライザの設計と実現
- インターネットQoSビジュアライザにおけるQoS測定方法
- プロセス分解代数に基づくデータフロー図の段階的詳細化における変換の一意性と再利用性
- プロセス分解代数に基づくデータフロー図の段階的詳細化
- プロセス分解代数に基づくデータフロー図の段階的詳細化システムの設計と実現
- インターネットにおけるQoSビジュアライザ
- リアクティブ・データフロー型ドキュメントブラウザの実現
- リアクティブ・データフロー型ドキュメントブラウザのためのドキュメント・プログラミング
- 経路依存フローグラフを用いた意味構成管理モデル
- プレスブルガー算術を用いたInfeasible Pathの検出
- 経路依存フローグラフのデータフロー計算に基づくプログラムスライス作成法
- PVMプログラムのための再演型デバッガの実現と評価
- 区間設定可能なプログラムスライシングを用いたソフトウェア部品の作成
- 区間限定スライスを用いた再利用部品抽出手法の評価
- プレスブルガー算術を用いたInfeasible Path検出の高速化技法
- 区間限定スライスを用いた部品作成システムの評価
- 区間限定スライスを用いた部品作成システムの評価
- 要求駆動型再演機能を持つPVMプログラムデバッガXdbxR/PVM
- 経路依存フローグラフを用いたプログラムスライシング
- 適応的再演型ロック命令を用いた並列プログラムデバッガの実現
- プレスブルガー算術を用いたInfeasible Path検出の高速化技法
- 重み付き依存グラフを用いたソフトウェア部品の洗練
- プログラム・スライシングによるソフトウェア部品の作成
- WSクラスタ型並列IPルータ実験システムCORErouter-I
- 並列IPルータCORErouterにおける並列パケットフィルタ機構の提案
- 非同期通信環境における連続データのQoS保証に関する考察
- WSクラスタを用いたCORErouterプロトタイプの評価
- WSクラスタを用いたCORErouterプロトタイプの構成
- 柔軟でスケーラブルな高性能並列ルータCORErouterの基本構想
- 適応的再演型並列プログラムデバッガのPVM上での実現
- 適応的再演型並列プログラムデバッガのPVM上での実現
- メッセージパッシング型並列プログラムのための適応的再演型デバッガdbxR-II
- 適応的再演型ロック命令を用いた並列プログラムデバッガ
- 適応型ロック機構を用いた並行プロセスのコスケジューリングについて
- ソフトウェア・マイグレーション向き計算環境モデルの作成法
- ソフトウェア・マイグレーション向き計算環境モデルを用いたソフトウェアの実装法
- ソフトウェア・マイグレーションのための計算環境のモデル化
- 広域時計を用いた等時性保証通信の実現法
- 並列分散型連続メディア処理モデルHEARTSにおける同時性保証機構
- 細粒度オブジェクト空間を用いたCASEデータベースのトランザクション処理モデル
- リアクティブ・データフロー型ドキュメントブラウザにおけるユーザレベルへの適応表示制御
- リアクティブデータフロー・モデルの基づくドキュメントブラウザの設計と実現
- ソフトウェア意味構成管理モデルにおけるスライシング技法を用いたプログラム解析
- 経路依存フローグラフを用いたInfeasible Path検出における計算量削減法
- 経路依存フローグラフを用いたプログラム解析システム
- 経路依存フローグラフを用いたプログラム・スライシング
- 経路依存フローグラフを用いたプログラム・スライシング
- 経路依存フローグラフを用いたInfeasible Path検出法
- 経路依存フローグラフを用いたプログラム・スライシング
- 経路依存フロ-グラフを用いたプログラム解析 (知的ソフトウェア技術)
- 意味構成管理システムを用いた修正プログラムにおける相互干渉の検出
- ベルリン工科大学リアルタイムシステムとロボティクス研究室に留学して(海外,ラボラトリーズ)