首页    期刊浏览 2024年11月28日 星期四
登录注册

文章基本信息

  • 标题:Multivariate Amortised Resource Analysis for Term Rewrite Systems
  • 本地全文:下载
  • 作者:Martin Hofmann ; Georg Moser
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2015
  • 卷号:38
  • 页码:241-256
  • DOI:10.4230/LIPIcs.TLCA.2015.241
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:We study amortised resource analysis in the context of term rewrite systems. We introduce a novel amortised analysis based on the potential method. The method is represented in an inference system akin to a type system and gives rise to polynomial bounds on the innermost runtime complexity of the analysed rewrite system. The crucial feature of the inference system is the admittance of multivariate bounds in the context of arbitrary data structures in a completely uniform way. This extends our earlier univariate resource analysis of typed term rewrite systems and continues our program of applying automated amortised resource analysis to rewriting.
  • 关键词:program analysis;amortised analysis; term rewriting;multivariate bounds
国家哲学社会科学文献中心版权所有