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.
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).