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.

Exponential Automatic Amortized Resource Analysis

ETAPS is a confederation of several conferences, each with its own Programme Committee and Steering Committee. ETAPS is the most important and visible annual European event related to software sciences. Altogether, more than 500 researchers participate in this event every year. The confederated conferences cover various aspects of software systems, ranging from theoretical foundations to programming language developments, compiler advancements, analysis tools, formal approaches to software engineering, and security.

A gather.town room will be open during the whole conference, which can be found here:

https://gather.town/app/nSgVv0DDYoCkmdkP/ETAPS2021

Password: Luxembourg2021

This can be used to meet in the coffee breaks.

 PDF's of the papers are available on https://etaps.org/2021/programme