項書き換えに基づく計算量解析の自動化

• 資料種別: 文書・図像類
• タイトル: 項書き換えに基づく計算量解析の自動化
• 著者・編者: 廣川, 直
• 著者標目: 廣川, 直
• 出版年月日等: 2010-05-26
• 出版年（W3CDTF）: 2010-05-26
• 並列タイトル等: Automated Complexity Analysis for Term Rewriting
• タイトル（掲載誌）: 科学研究費補助金研究成果報告書
• 掲載ページ: 1-4
• 本文の言語コード: jpn
• 件名標目: 項書き換え; 計算モデル; 計算量
• 対象利用者: 一般
• 一般注記: 探索やソートアルゴリズムを開発したとき、「入力の大きさに対しどれくらいの速度(ステップ数) で動作するか」という自然な疑問が生じる。現在に至るまで時間的計算量は、プログラムごとに手作業で解析するものと認識されていた。本研究では、関数型プログラムの計算モデルである項書き換え系に対して、解析を自動化する強力な理論を構築した。さらにそれに基づく計算量自動解析ツールを実装した。既存手法との比較実験を行った結果、解析精度の劇的な向上が確認された。 : 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; 研究分野：総合領域; 科研費の分科・細目：情報学・情報学基礎; identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/9038
• 記録形式（IMT）: application/pdf
• 一次資料へのリンクURL: https://dspace.jaist.ac.jp/dspace/bitstream/10119/9038/1/20800022seika.pdf
• オンライン閲覧公開範囲: 限定公開
• 連携機関・データベース: 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）; https://irdb.nii.ac.jp
• 提供元機関・データベース: 北陸先端科学技術大学院大学 : JAIST学術研究成果リポジトリ