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