Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2012 / Oberseminar / Diego Alonso, On the Limits of the Classical Approach of the Cost Analysis


Inhaltsbereich

Diego Alonso, On the Limits of the Classical Approach of the Cost Analysis

TCS Oberseminar, 25.05., 14h
Wann 14:15 15:15 25.05.2012
von bis
Wo L109
Termin übernehmen vCal
iCal

Diego Alonso

On the Limits of the Classical Approach of the Cost Analysis

Description

 

Several cost analysers follow the classical approach to cost analysis. In this approach, the cost of each program's module is specified as a function of the program's inputs sizes, and these functions are inferred by

  1. transforming each program module into a system of recurrence relations,  that model the program's cost: and 
  2. solving these recurrence relations, which can be done with common computer algebra systems. 

In this paper we show the limits of this approach, namely, that analysers following it obtain asymptotically imprecise results for certain programs. We then present another approach for the verification and synthesis of cost bound functions based on first-order Satisfiability and Quantifier Elimination that can infer precise results for those programs.

 

 

Artikelaktionen

abgelegt unter:

Funktionsleiste