抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
Dyck-到達可能性は,プログラム解析のための基本的定式化であり,それは,機能呼び出し/リターンおよびフィールド書き込み/読書のような適切にマッチした構文プログラム特性を把握するために広く使用されてきた。二方向Dyck-到達可能性は,各エッジu→(i)が対応する近接親子「_i」によってラベル付けされた逆エッジv→iuを随伴する二方向グラフ上のDyck-到達可能性の緩和であり,その逆も同様である。実際に,エイリア解析のような多くのクライアント分析は,二方向Dyck-到達可能性定式化を採用する。双方向性Dyck到達可能性は,最適可到達性アルゴリズムを許容する。特に,nノードとmエッジを有するグラフを与えて,最適二方向Dyck-到達可能性アルゴリズムは,O(m)時間における全ペア到達可能性情報を計算する。本論文は,二方向Dyck-到達可能性の動的バージョンに焦点を合わせた。特に,エッジ挿入と欠失のシーケンスの下で二方向グラフにおける全対Dyck-到達可能性情報を維持する問題を考察した。動的二方向Dyck-到達可能性は,コード変化の存在下で多くのプログラム解析問題を定式化できる。残念ながら,動的グラフ到達可能性問題を解明することは挑戦的である。例えば,トランジット閉鎖を維持するためにさえ,最速決定論的動的アルゴリズムは,O(1)クエリ時間を達成するために,O(n2)更新時間を必要とする。全対Dyck-到達可能性は遷移閉鎖の一般化である。増分計算に関する広範囲な研究にもかかわらず,最悪ケース保証によるプログラム解析のための動的グラフアルゴリズムに関するアルゴリズム開発はない。本研究では,ギャップを埋め,二方向グラフ上のDyck到達可能性に対する最初の動的アルゴリズムを提案した。この動的アルゴリズムは,O(n=α(n))時間における各グラフ更新(すなわち,エッジ挿入と削除)を扱うことができ,O(1)時間での全ての対到達性クエリをサポートし,そこでは,α(n)は逆Ackermann関数である。著者らは,エイリア解析に関する著者らの動的アルゴリズムおよびJavaのためのコンテキスト感受性データ依存性解析を実施し,評価した。O(m)-時間最適二方向Dyck-到達可能性アルゴリズムと最近のインクリメンタルデータログソルバに基づく直接的手法に対する動的アルゴリズムを比較した。実験結果は,著者らのアルゴリズムが両方のアプローチで桁の高速化を達成することを示した。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】
