INSTITUTE OF CYBERNETICS at TALLINN UNIVERSITY OF TECHNOLOGY
top

Seminariteade / Seminar announcement


Speaker: Olha SHKARAVSKA, Institut für Informatik, Ludwig-Maximilians-Universität München
Place: Room B101, Cybernetica Bldg, Akadeemia tee 21, Tallinn, Estonia
Time: Thursday, May 26, 2005, 14:00

"Amortised analysis of heap consumption"

Abstract

The type-theoretical kernel of the Mobile Resource Guarantees framework consists of a type system which allows to infer linear bounds of heap consumption for functional programs.

The type system, proposed by Hofmann and Jost, may be considered as a banker's algorithm for heap. The term "banker's algorithm" is used in Amortised Analysis of resource consumption. In this method one associates with a node of data structure, such as an element of a list, a certain amount of a resource called a credit.

In the Hofmann-Jost system these credits are numerical constants. We consider the ways of generalisation of their approach, for instance, by introducing credits as functions. This allows to infer non-linear resource bounds, including polynomial and logarithmic ones.

Valid CSS! Valid XHTML 1.0 Strict

top
© Institute of Cybernetics at TUT, Akadeemia tee 21, 12618 Tallinn, Estonia    Phone: +372 620 4150   Fax: +372 620 4151

03/05/2005 10:26 EEST webmaster ( at ) cs.ioc.ee