LSV Seminar

The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.

The seminar is open to public and does not require any form of registration.

Past Seminars

Questions de théorie des jeux et de convexité abstraite en analyse statique de programme

Visit website for this news | Export event in iCalendar format

Date
Tuesday, November 04 2008 at 11:00AM
Place
Salle de Conférence (Pavillon des Jardins)
Speaker
Stéphane Gaubert (INRIA et CMAP, École Polytechnique, Palaiseau, France)

Le but de cet exposé est de donner quelques exemples d'application de techniques d'optimisation et de théorie des jeux en analyse statique de programme par interprétation abstraite.

On présentera tout d'abord une correspondance entre les problèmes de point fixe rencontrés en interprétation abstraite et ceux que l'on rencontre en théorie des jeux à somme nulle. Cette correspondance permet d'adapter des algorithmes inspirés de la théorie des jeux ou du contrĂ´le tels que l'itération sur les politiques, mais le caractère "expansif" des opérateurs de point fixe, qui se traduit par la présence d'un taux d'actualisation négatif, pose des difficultés algorithmiques inédites. On discutera notamment le problème du calcul du point fixe minimal (ou de la vérification de la minimalité d'un point fixe) à l'aide de techniques de théorie de Perron-Frobenius non-linéaire.

On montrera ensuite comment des idées empruntées à l'analyse convexe abstraite permettent de définir des classes de domaines généralisant le domaine des "templates" introduit par Manna et ses collaborateurs. On traitera spécialement du domaine des polyèdres max-plus ou tropicaux.

Ces résultats sont issus de travaux en collaboration avec A. Adje (LIX/MeASI), X. Allamigeon (EADS), E. Goubault et S. Putot (CEA/MeASI).


About LSV

Agenda

Export agenda in iCalendar format | Past seminars

Tue, Jan 29
Tue, Feb 5
Tue, Feb 19

Past seminars