Proof Theory at Work: Complexity Analysis of Term Rewrite Systems

Abstract

This thesis is concerned with investigations into the "complexity of term rewriting systems". Moreover the majority of the presented work deals with the "automation" of such a complexity analysis. The aim of this introduction is to present the main ideas in an easily accessible fashion to make the result presented accessible to the general public. Necessarily some technical points are stated in an over-simplified way.

Cumulative Habilitation Thesis, submitted to the University of Innsbruck

References in corpus (1)

• The Derivational Complexity Induced by the Dependency Pair Method

Cited by in corpus (5)

• A Combination Framework for Complexity
• A New Order-theoretic Characterisation of the Polytime Computable Functions
• Polynomial Path Orders: A Maximal Model
• A Complexity Preserving Transformation from Jinja Bytecode to Rewrite Systems
• A Path Order for Rewrite Systems that Compute Exponential Time Functions (Technical Report)