JAIST Repository >
b. 情報科学研究科・情報科学系 >
b50. 科学研究費助成事業研究成果報告書 >
2009年度 >

このアイテムの引用には次の識別子を使用してください: http://hdl.handle.net/10119/9038

タイトル: 項書き換えに基づく計算量解析の自動化
その他のタイトル: Automated Complexity Analysis for Term Rewriting
著者: 廣川, 直
著者(別表記): HIROKAWA, NAO
キーワード: 項書き換え
計算モデル
計算量
発行日: 26-May-2010
抄録: 探索やソートアルゴリズムを開発したとき、「入力の大きさに対しどれくらいの速度(ステップ数) で動作するか」という自然な疑問が生じる。現在に至るまで時間的計算量は、プログラムごとに手作業で解析するものと認識されていた。本研究では、関数型プログラムの計算モデルである項書き換え系に対して、解析を自動化する強力な理論を構築した。さらにそれに基づく計算量自動解析ツールを実装した。既存手法との比較実験を行った結果、解析精度の劇的な向上が確認された。 : Time complexity is one of the most fundamental properties of programs. So far time complexity of programs has been analyzed manually. In this project we developed a powerful theoretical framework for automating runtime complexity analysis of term rewrite systems, which are underlying computational models for declarative programs. Moreover, we have implemented a complexity analyzer based on our framework. Experiments showed that our method outperforms existing ones in its analytical precision.
記述: 研究種目:若手研究(スタートアップ)
研究期間:2008~2009
課題番号:20800022
研究者番号:50467122
研究分野:総合領域
科研費の分科・細目:情報学・情報学基礎
言語: jpn
URI: http://hdl.handle.net/10119/9038
出現コレクション:2009年度 (FY 2009)

このアイテムのファイル:

ファイル 記述 サイズ形式
20800022seika.pdf215KbAdobe PDF見る/開く

当システムに保管されているアイテムはすべて著作権により保護されています。

 


お問い合わせ先 : 北陸先端科学技術大学院大学 研究推進課図書館情報係