COMPUTER SCIENCE COLLOQUIUM

A Framework for Automated Analysis of Runtime Complexity

Fabian Emmes LuFG I2 RWTH Aachen University, Germany

Thursday, 10 March, 2011 at 15:15 U51

ABSTRACT

One very successful approach to analyze the termination of programs is to translate them to term rewrite systems and then use rewriting techniques to conclude termination of the rewrite system and hence, the original program.

A very natural extension of this idea is to use similar transformations from programs to term rewriting and then analyze the runtime complexity of the resulting rewrite system.

In this talk, we present a novel framework for the latter, which lifts several ideas from automated termination analysis to automated complexity analysis. Using this approach, it is now possible to obtain polynomial upper bounds for a large class of term rewrite systems.

Host: Peter Schneider-Kamp

---

SDU HOME | IMADA HOME | Previous Page

---

Daniel Merkle