ISR 2010

5th International School on Rewriting

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

Complexity Analysis of Term Rewrite Systems


Georg Moser (University of Innsbruck, Austria)


(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.