The complexity of term rewrite systems

Thomas Powell

(University of Innsrbuck)

Term rewrite systems form a powerful abstract model of computation, which can be used to analyse real-world programming languages. In this talk I will focus on the development of methods to obtain complexity bounds on term rewrite systems. Rather than presenting completed work, I will describe some new ideas and directions in which I feel that progress could be made. In particular I shall discuss the application of proof interpretations to automatically extract complexity bounds from termination proofs, and will also talk about notions of complexity for higher-type rewrite systems.
Thursday 4th December 2014, 12:00
Board Room
Department of Computer Science