Multivariate Amortized Resource Analysis
Multivariate Amortized Resource Analysis
复制标题
DOI：
10.1145/2362389.2362393
复制
发表时间：
2012-10-01
影响因子：
1.3
通讯作者：
Hofmann, Martin
中科院分区：
文献类型：
--
作者：
Hoffmann, Jan;Aehlig, Klaus;Hofmann, Martin
我们研究的问题，自动分析的最坏情况下的资源使用的程序与几个参数。现有的自动分析的基础上摊销或大小的类型约束的资源使用或结果大小的这样一个过程的参数的大小的一元函数的总和。在这篇文章中，我们将其推广到任意的多元多项式函数，从而允许的形式mn的界限，必须严重高估了m（2）+ n（2）之前。我们的框架甚至包括像Sigma（i，j）这样的边界
We study the problem of automatically analyzing the worst-case resource usage of procedures with several arguments. Existing automatic analyses based on amortization or sized types bound the resource usage or result size of such a procedure by a sum of unary functions of the sizes of the arguments.In this article we generalize this to arbitrary multivariate polynomial functions thus allowing bounds of the form mn which had to be grossly overestimated by m(2) + n(2) before. Our framework even encompasses bounds like Sigma(i,j