6th International School on Rewriting >> Automated Complexity Analysis of Term Rewriting Systems

6th International School on Rewriting

July 16th - 20th, 2012. Valencia, Spain


ACA: Automated Complexity Analysis of Term Rewriting Systems


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 assert 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 some of these results and present recent results on automatic complexity analyis of rewrite systems. Furthermore we link these results to competing techniques to analyse the complexity of programs automatically.

<< Back to Previous Page.