Campus Event Calendar
Event Entry
New for: D2, D3
What and Who
Automated Complexity Analysis Based on the Dependency Pair Method
Georg Moser
University of Innsbruck
Talk
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI
Public Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 26 October 2010
14:00
60 Minutes
Warning: Date has changed!
Warning: Time has changed!
E1 4
019
Saarbrücken
Abstract
Term rewriting is a conceptually simple but powerful
abstract model of computation that underlies much of declarative
programming. In order to assess the complexity of a (terminating)
rewrite system it is natural to look at the maximal length of
derivation sequences. The "runtime complexity function" relates the
length of the longest derivation sequence to the size of the arguments
of the initial term, where the arguments are supposed to be in normal
form.
In this talk I will present a variant of the dependency pair method
for analysing runtime complexities of term rewrite systems
automatically. This technique, called "weak dependency pair method"
is easy to implement, but significantly extends the analytic power of
existing methods. In particular my talk will focus on very recent
extension of the method that suitably adapts "context-sensitive
rewriting" for the area of complexity of rewriting.
abstract model of computation that underlies much of declarative
programming. In order to assess the complexity of a (terminating)
rewrite system it is natural to look at the maximal length of
derivation sequences. The "runtime complexity function" relates the
length of the longest derivation sequence to the size of the arguments
of the initial term, where the arguments are supposed to be in normal
form.
In this talk I will present a variant of the dependency pair method
for analysing runtime complexities of term rewrite systems
automatically. This technique, called "weak dependency pair method"
is easy to implement, but significantly extends the analytic power of
existing methods. In particular my talk will focus on very recent
extension of the method that suitably adapts "context-sensitive
rewriting" for the area of complexity of rewriting.
Contact
Jennifer Müller
900
--email hidden
passcode not visible
logged in users only
Jennifer Müller, 10/25/2010 09:28
Jennifer Müller, 10/20/2010 11:45
Anna-Lisa Overhoff, 10/20/2010 11:31 -- Created document.
Jennifer Müller, 10/20/2010 11:45
Anna-Lisa Overhoff, 10/20/2010 11:31 -- Created document.