Automated Complexity Analysis for Term Rewriting
Automated Complexity Analysis for Term Rewriting
术语重写的自动复杂性分析
批准号：
20800022
负责人：
HIROKAWA Nao
金额：
$1.62万
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (Start-up)
财政年份：
2008
资助国家：
日本
项目状态：
已结题
起止时间：
2008 至 2009
中文摘要
翻译
点击翻译按钮获取中文摘要
英文摘要
探索やソートアルゴリズムを開発したとき、「入力の大きさに対しどれくらいの速度(ステップ数)で動作するか」という自然な疑問が生じる。現在に至るまで時間的計算量は、プログラムごとに手作業で解析するものと認識されていた。本研究では、関数型プログラムの計算モデルである項書き換え系に対して、解析を自動化する強力な理論を構築した。さらにそれに基づく計算量自動解析ツールを実装した。既存手法との比較実験を行った結果、解析精度の劇的な向上が確認された。
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
DOI：
--
发表时间：
2008
期刊：
影响因子：
--
作者：
[Nao Hirokawa, Aart Middeldorp, Harald Zankl]
通讯作者：
Harald Zankl
Complexity, Graphs, and the Dependency Pair Method
复杂性、图形和依赖对方法
复杂性、图形和依赖对方法
DOI：
--
发表时间：
2008
期刊：
影响因子：
--
作者：
[Nao Hirokawa, Georg Moser]
通讯作者：
Georg Moser
The Subterm Criterion in Complexity Analysis
复杂性分析中的子项准则
复杂性分析中的子项准则
DOI：
--
发表时间：
2009
期刊：
影响因子：
--
作者：
[Nao Hirokawa, Georg Moser]
通讯作者：
Georg Moser
Uncurrying for Termination
取消柯里化以终止
取消柯里化以终止
DOI：
--
发表时间：
2008
期刊：
影响因子：
--
作者：
[Nao Hirokawa, Aart Middeldorp, Harald Zankl]
通讯作者：
Harald Zankl
電子情報通信学会 知識ベース 7群1編「ソフトウェア基礎」2章「定理証明と検証法」3節「SAT」執筆
IEICE 知识库，第 7 组，第 1 卷，“软件基础知识”，第 2 章，“定理证明和验证方法”，第 3 节，“SAT”写作
IEICE 知识库，第 7 组，第 1 卷，“软件基础知识”，第 2 章，“定理证明和验证方法”，第 3 节，“SAT”写作
DOI：
--
发表时间：
2010
期刊：
影响因子：
--
作者：
[Nao Hirokawa, Georg Moser, 廣川直, 廣川直]
通讯作者：
廣川直
共 8 条
Rewriting Techniques for Non-Deterministic Computation
-
批准号：22700009
-
项目类别：Grant-in-Aid for Young Scientists (B)
-
资助金额：$2.41万
-
财政年份：2010
-
负责人：HIROKAWA Nao
-
依托单位：
海外基金