# 5th International School on Rewriting

## 3 – 8 July 2010, Drift 21, Utrecht, Netherlands

### Complexity Analysis of Term Rewrite Systems

#### Lecturer

Georg Moser (University of Innsbruck, Austria)#### Introduction

(advanced track, 3 lecture sessions)

For a terminating term rewrite system (TRS for short), we can consider the following abstract problem:

How many replacement steps can we perform till no more replacement is possible?

Termination asserts that this problem is well-defined. This question
entails investigations into the *complexity* of term rewrite systems.
A TRS is considered of higher complexity, if the number of possible
rewrite steps is larger. In recent years this sub-field of rewriting
has been thoroughly revived and challenging problems could be solved.
In some cases, these observations can be extended to characterisations
of complexity classes, for instance of the class of functions
computable in polynomial time.

We review these results and present a mixture of established
*folklore* results on upper and lower complexity bounds as well as
results on the border of our current understanding. Moreover, various
approaches of an automated complexity analysis are discussed.

#### Material

- preparation: install Tyrolean Complexity Tool (linux binary in the tgz file below).
- tgz-file with course material (unpacks to a directory GM).
- material also available from this web-site