Proof Theory at Work: Complexity Analysis of Term Rewrite Systems

2009/07/31 by Moser, Georg · 1 citation
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Software Engineering (cs.SE) #Symbolic Computation (cs.SC)

paper · doi:10.48550/arxiv.0907.5527

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.

Cited by

• Resource-Aware Hybrid Quantum Programming with General Recursion and Quantum Control

Related

• Automated Complexity Analysis Based on the Dependency Pair Method
• The complexity of normal form rewrite sequences for Associativity
• A Combination Framework for Complexity
• Efficient Implementation of Rewriting Revisited Technical Report
• Analysing Parallel Complexity of Term Rewriting