This paper presents a new approach for automatically deriving worst-case resource bounds
for C programs. The described technique combines ideas from amortized analysis and …

Verified compilers guarantee the preservation of semantic properties and thus enable formal
verification of programs at the source level. However, important quantitative properties such …

We present TiML (Timed ML), an ML-like functional language with time-complexity
annotations in types. It uses indexed types to express sizes of data structures and upper …

We show how the complexity of higher-order functional programs can be analysed
automatically by applying program transformations to a defunctionalised versions of them …

We present a Separation Logic with space credits for reasoning about heap space in a
sequential call-by-value lambda-calculus equipped with garbage collection and mutable …

Union-Find is a famous example of a simple data structure whose amortized asymptotic time
complexity analysis is nontrivial. We present a Coq formalization of this analysis, following …

Type-based amortised resource analysis following Hofmann and Jost—where resources are
associated with individual elements of data structures and doled out to the programmer …

Garbage collectors relieve the programmer from manual memory management, but lead to
compiler-generated machine code that can behave differently (eg out-of-memory errors) …

We present SL♢, a Separation Logic that allows controlling the heap space consumption of
a program in the presence of dynamic memory allocation and garbage collection. A user of …

This paper introduces a new methodology for the complexity analysis of higher-order
functional programs, which is based on three ingredients: a powerful type system for size …