Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Automated Complexity Analysis of Rewrite Systems
Speaker:Florian Frohn
coming from:RWTH Aachen
Speakers Bio:Florian Frohn is a research assistant at Lehr- und Forschungsgebiet Informatik 2 at RWTH Aachen. In December 2018, he successfully defended his PhD thesis.
Event Type:SWS Colloquium
Visibility:D1, D2, D3, INET, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 22 January 2019
Duration:60 Minutes
Many approaches to analyze the complexity of programs automatically are based on transformations into integer or term rewrite systems. However, state-of-the-art tools that analyze the worst-case complexity of rewrite systems are restricted to the inference of upper bounds. In this talk, the first techniques for the inference of lower bounds on the worst-case complexity of integer and term rewrite systems are introduced. While upper bounds can prove the absence of performance-critical bugs, lower bounds can be used to find them.

For term rewriting, the power of the presented technique gives rise to the question whether the existence of a non-constant lower bound is decidable. Thus, the corresponding decidability results are also discussed in this talk.

Finally, to see the practical value of complexity analysis techniques for rewrite systems, we will have a glimpse at the transformation from Java programs to integer rewrite systems that is implemented in the tool AProVE.
Name(s):Susanne Girard
Video Broadcast
Video Broadcast:YesTo Location:Saarbr├╝cken
To Building:E1 5To Room:029
Meeting ID:
Tags, Category, Keywords and additional notes
Attachments, File(s):
Susanne Girard/MPI-SWS, 01/16/2019 11:25 AM
Last modified:
Uwe Brahm/MPII/DE, 01/22/2019 07:01 AM
  • Susanne Girard, 01/16/2019 11:32 AM -- Created document.