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

Material type: 文書・図像類

Author: 廣川, 直

Publisher: -

Publication date: 2010-05-26

Material Format: Digital

Capacity, size, etc.: -

NDC: -

View All

Notes on use

Note (General)：: 探索やソートアルゴリズムを開発したとき、「入力の大きさに対しどれくらいの速度(ステップ数) で動作するか」という自然な疑問が生じる。現在に至るまで時間的計算量は、プログラムごとに手作業で解析するものと認識されていた。本研究では、関数型プログラムの計算モデルである項書き換え系に対して、解析を自動化する...

Search by Bookstore

Holdings of Libraries in Japan

This page shows libraries in Japan other than the National Diet Library that hold the material.

List of Cooperating Institutions and Databases

Please contact your local library for information on how to use materials or whether it is possible to request materials from the holding libraries.

other

JAIST Repository
Digital
You can check the holdings of institutions and databases with which 学術機関リポジトリデータベース（IRDB）（機関リポジトリ） is linked at the site of 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）.
JAIST Repository

Search by Bookstore

Bibliographic Record

You can check the details of this material, its authority (keywords that refer to materials on the same subject, author's name, etc.), etc.

Digital

Material Type: 文書・図像類
Title: 項書き換えに基づく計算量解析の自動化
Author/Editor: 廣川, 直
Author Heading: 廣川, 直
Publication Date: 2010-05-26
Publication Date (W3CDTF): 2010-05-26
Alternative Title: Automated Complexity Analysis for Term Rewriting
Periodical title: 科学研究費補助金研究成果報告書
Pages: 1-4
Text Language Code: jpn
Subject Heading: 項書き換え
計算モデル
計算量
Target Audience: 一般
Note (General): 探索やソートアルゴリズムを開発したとき、「入力の大きさに対しどれくらいの速度(ステップ数) で動作するか」という自然な疑問が生じる。現在に至るまで時間的計算量は、プログラムごとに手作業で解析するものと認識されていた。本研究では、関数型プログラムの計算モデルである項書き換え系に対して、解析を自動化する強力な理論を構築した。さらにそれに基づく計算量自動解析ツールを実装した。既存手法との比較実験を行った結果、解析精度の劇的な向上が確認された。 : 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
Format (IMT): application/pdf
Source: https://dspace.jaist.ac.jp/dspace/bitstream/10119/9038/1/20800022seika.pdf
https://dspace.jaist.ac.jp/dspace/bitstream/10119/9038/1/20800022seika.pdf
Access Restrictions: 限定公開
Data Provider (Database): 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）
https://irdb.nii.ac.jp
Original Data Provider (Database): 北陸先端科学技術大学院大学 : JAIST学術研究成果リポジトリ