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

In this paper we present a combination framework for the automated polynomial complexity
analysis of term rewrite systems. The framework covers both derivational and runtime …

The class of basic feasible functionals (BFF) is the analog of FP (polynomial time functions)
for type-2 functionals, that is, functionals that can take (first-order) functions as arguments …

In this paper we present a simple technique for analysing the runtime complexity of rewrite
systems. In complexity analysis many techniques are based on reduction orders. We show …

In this paper we show how the runtime complexity of imperative programs can be analysed
fully automatically by a transformation to term rewrite systems, the complexity of which can …

Analyzing Runtime Complexity via Innermost Runtime Complexity Page 1 Analyzing Runtime
Complexity via Innermost Runtime Complexity Florian Frohn1 Jürgen Giesl1 1RWTH Aachen …

We define the class of constrained cons-free rewriting systems and show that this class
characterizes P, the set of languages decidable in polynomial time on a deterministic Turing …

We propose a notion of complexity for oriented conditional term rewrite systems satisfying
certain restrictions. This notion is realistic in the sense that it measures not only successful …

We propose a new order-theoretic characterisation of the class of polytime computable
functions. To this avail we define the small polynomial path order (sPOP* for short). This …

Constructor rewriting systems are said to be cons-free if, roughly, constructor terms in the
right-hand sides of rules are subterms of constructor terms in the left-hand side; the …