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:Complexity Analysis for Term Rewriting by Integer Transition Systems
Speaker:Florian Frohn
coming from:RWTH Aachen
Speakers Bio:
Event Type:Talk
Visibility:D1, D2, D3, INET, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Thursday, 24 January 2019
Duration:60 Minutes
Building:E1 5
While programs operating on integers are akin to integer
transition systems (ITSs), programs operating on data structures
can be transformed to term rewrite systems (TRSs) in many
cases. In the last years, powerful complexity analysis techniques
for ITSs have been developed. To make them available for the
analysis of programs operating on data structures, we present a
suitable transformation from TRSs to ITSs. It first uses a novel
sufficient criterion to prove that, independently of the
evaluation strategy under consideration, the complexity of the
analyzed TRS is bounded by its complexity w.r.t. eager
evaluation. Next, the TRS is transformed into a recursive program
over the natural numbers. As ITSs are restricted to tail
recursion, we then show how to analyze the resulting recursive
program iteratively. In each iteration, a tail-recursive function
is analyzed by existing complexity analysis tools for ITSs. Then,
calls to this function are eliminated, so that non-tail-recursive
program parts become tail-recursive and can be analyzed in the
next iteration.
Name(s):Jennifer Müller
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
Jennifer Müller/MPI-INF, 01/21/2019 09:03 AM
Last modified:
Uwe Brahm/MPII/DE, 01/24/2019 07:01 AM
  • Jennifer Müller, 01/21/2019 09:04 AM -- Created document.