Kim G. Larsen

CISS, Department of Computer Science, Aalborg University, Denmark.

Time: Thursday 9.12.2004, 13:00
Place: Room B2-109, Fr. Bajersvej 7

Priced Timed Automata Decidability Results, Algorithms and Applications
or
Four Different Ways of Winning Vector-Race

Since 2000 -- and within the European projects VHS and AMETIST -- timed automata technology has been applied to an increasing number of cost-optimizing scheduling problems. As a consequence the model or priced timed automata -- an extension of the classical timed automata model by Alur & Dill -- has been put forward and a number of optimization problems have been shown decidable while others are still open research topics. Effecient datastructures and algorithms have been developed and implemented for a number of the problems now to be found in the newly released UPPAAL CORA (www.cs.auc.dk/~behrmann/cora) dialect of UPPAAL.

The talk will give an introduction and suvey of state-of-the-art of the research area with occasional inspiration drawn from the overall most important problem of how to win vector-race.

The talk is based heavily on extensive collaboration with Gerd Behrmann, Jacob Illum Rasmussen, Emmanuel Fleury and others.