17 May 2018

Séminaire MOVE : Polynomial Invariants for Affine Programs, James Worrell (Oxford University)

Automatically generating invariants is a fundamental challenge in program analysis and verification. In this talk we give a select overview of previous work on this problem, starting with Michael Karr's 1976 algorithm for computing affine invariants for affine programs (i.e., programs in which all assignments are affine and which conditionals are abstracted by non-determinism) and proceeding to subsequent work on computing polynomial invariants for affine programs. We then present our main result-an algorithm to compute all polynomial invariants that hold at each location of a given a affine program. Our main tool is an algebraic result of independent interest: given a finite set of rational square matrices of the same dimension, we show how to compute the Zariski closure of the semigroup that they generate. This is joint work with Ehud Hrushovski, Joel Ouaknine, and Amaury Pouly.
17 May 2018, 10h3012h00
Salle de réunion du bâtiment modulaire BP5 (en bas de la BU), Luminy

Prochains évènements

Retour à l'agenda
31 May 2018

Séminaire MOVE : Nash equilibria in games on graphs with a public signal monitoring, Patricia Bouyer-Decitre (LSV, ENS Paris-Saclay, CNRS)

In this talk, I will start by presenting all basic material about games on graphs, which will be useful. I will then focus on pure Nash equilibria in such games on graphs, with an imperfect monitoring based on a public signal. In such games, deviations and players responsible for those deviations can be hard to detect and track. I will present a generic epistemic game abstraction, which conveniently allows to represent the knowledge of the players about these deviations, and give a characterization of Nash equilibria in terms of winning strategies in the abstraction. I will then explain how that abstraction helps providing algorithms for computing Nash equilibria for some payoff functions.

04 Jun08 Jun 2018

WorkShop DYNI : DCLDE 2018

l'équipe DYNI du LIS, UTLN, est heureuse de lancer en partenariat avec le Scripps Inst. le plus grand challenge de bioacoustique sous-marine (4 To, Atlantique et Pacifique) dans le cadre du congrès de Détection Classification Localisation & Estimation de Densité de mammifère marin que nous co-organisons avec Sorbonne Univ. en Juin.