Exponential Automatic Amortized Resource Analysis
Exponential Automatic Amortized Resource Analysis
复制标题
DOI：
10.1007/978-3-030-45231-5_19
复制
发表时间：
2020-04-17
期刊：
影响因子：
--
通讯作者：
Hoffmann J
中科院分区：
文献类型：
--
作者：
Kahn DM;Hoffmann J
自动摊销资源分析（AARA）是一种基于类型的技术，用于在AARA上的现有工作中推断出资源的界限。将AARA的扩展到保留技术好处的指数界，例如基于线性约束的组成性和有效的推理。第二种作为潜在函数的基础，在多项式AARA中起着与二项式系数相同的作用。指数版本和具有潜在功能的组合系统由Stirling数字和二项式系数形成。关于操作成本语义和代表性示例程序的分析，证明了新分析的有效性。
Automatic amortized resource analysis (AARA) is a type-based technique for inferring concrete (non-asymptotic) bounds on a program’s resource usage. Existing work on AARA has focused on bounds that are polynomial in the sizes of the inputs. This paper presents and extension of AARA to exponential bounds that preserves the benefits of the technique, such as compositionality and efficient type inference based on linear constraint solving. A key idea is the use of the Stirling numbers of the second kind as the basis of potential functions, which play the same role as the binomial coefficients in polynomial AARA. To formalize the similarities with the existing analyses, the paper presents a general methodology for AARA that is instantiated to the polynomial version, the exponential version, and a combined system with potential functions that are formed by products of Stirling numbers and binomial coefficients. The soundness of exponential AARA is proved with respect to an operational cost semantics and the analysis of representative example programs demonstrates the effectiveness of the new analysis.
登录
查看更多内容
影响因子：
1.1
作者：
FLAJOLET, P;SALVY, B;ZIMMERMANN, P
通讯作者：
ZIMMERMANN, P
影响因子：
--
作者：
Carbonneaux, Quentin;Hoffmann, Jan;Shao, Zhong
通讯作者：
Shao, Zhong
影响因子：
0.5
作者：
Albert, Elvira;Genaim, Samir;Masud, Abu Naser
通讯作者：
Masud, Abu Naser
DOI：
10.1145/2362389.2362393
发表时间：
2012-10-01
影响因子：
1.3
作者：
Hoffmann, Jan;Aehlig, Klaus;Hofmann, Martin
通讯作者：
Hofmann, Martin
影响因子：
--
作者：
Gulwani, Sumit;Mehra, Krishna K.;Chilimbi, Trishul
通讯作者：
Chilimbi, Trishul