Complexity Analysis of Term Rewrite Systems


title: Complexity Analysis of Term Rewrite Systems


abstract: Term rewriting is a conceptually simple, but powerful abstract model of computation.

The foundation of rewriting is equational logic and term rewrite systems (TRS for short) are conceivable as sets of directed equations. Rewriting underlies much of declarative programming  and has found applications in automated reasoning.

In order to assess the complexity of a  (terminating) TRS it is natural to look at the maximal length of derivations. Roughly such an analysis is conceivable as a worst-case complexity analysis of the functions computed by the given TRS. In the talk I will review well-established results in this area, but also present recent results on automatable techniques that verify that the given TRS admits atmost polynomial (in the size of the start term) lengths of derivations.

A A A | Print | Imprint | Sitemap | Contact
zum Seitenanfang