文献

J-GLOBAL ID：202002243047446101   整理番号：20A2733805

交換性のオンライン検証【JST・京大機械翻訳】

Online verification of commutativity

著者 (3件)： Kabra Aditi (Carnegie Mellon University, USA) ,  Geisler Dietrich (Cornell University, USA) ,  Sampson Adrian (Cornell University, USA)
資料名： ACM Proceedings  (ACM Proceedings)
号： TAPAS 2020  ページ： 10-19  発行年： 2020年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 変換のシステムは,暗黙型変換関数のグラフのような多くのプログラミングシステムで発生する。これらのダイアグラムは,同じソースから同じ目的への変換の任意の経路を構成することは,同じ結果をもたらすということを確実にすることが重要である。しかし,可換性を検証するための直接的なアプローチは,サイクルを終了しなければならず,従って,指数関数的時間でも実行しなければならない。以前の研究は,O(|V|4|E|2)時間における非環状ダイアグラムの特殊事例における可換性を検証する方法を示し,これはバッチアルゴリズムであるが,全ダイアグラムは時間前に既知である。著者らは,新しいエッジを加えるとき,交換ダイアグラムが可換のままであることを,効率的に検証するオンラインアルゴリズムを提示する。新しい増分アルゴリズムは,O(|V|2(|E|+|V|))時間で動作する。パスの同等性をチェックする場合,O(|V|4)時間で動作する最適化も提示するが,同等性チェックの最小可能な数に減少する。アルゴリズムを実装し,それらをバッチベースラインと比較し,幾何学型に対するドメイン固有言語のコンパイラにおける実用的応用を示した。大規模ダイヤグラムに対するアルゴリズムのスケーラビリティを研究するために,著者らは,それらを適用して,キュレンシー変換グラフにおける不一致を発見した。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  幾何学 ,  最適化 ,  互換性 ,  コンパイラ ,  指数関数 ,  プログラミングシステム ,  基準線 ,  等価性
準シソーラス用語： オンラインアルゴリズム ,  ダイアグラム ,  *オンライン ,  ドメイン固有言語 , 【Automatic Indexing@JST】

著者キーワード (3件)： 自動型変換 ,  通勤図 ,  オンライン検証

分類 (1件)： 計算機システム開発  (JD02010R)

タイトルに関連する用語 (2件)： オンライン ,  検証