Date(s) : 27/11/2014 iCal
11 h 00 min - 12 h 00 min
J’exposerai des résultats récents à l’intersection entre mes travaux sur les graphes d’interaction et ceux concernant la complexité.
Mon travail sur les graphes d’interaction m’a mené à une construction systématique de modèles de la logique linéaire basée sur la notion de « graphage » — des réalisations de graphes par des fonctions mesurables. Intuitivement, un graphage est un graphe dont les sommets sont des ensembles mesurables et les arêtes sont « réalisées » par des fonctions mesurables. Ces modèles sont caractérisés par un monoide de fonctions (mesurables) qui décrit les différents manières de réaliser une arête.
Je montrerai que le choix de ce monoide correspond à imposer des contraintes de complexité. Cette correspondance est illustrée par l’obtention de modèles de MALL avec des exponentielles (très) faibles où le type des prédicats sur les entiers binaires !Nat_2 ⊸ Bool caractérise des classes de complexité telles que les languages réguliers, L (logspace), NL, Ptime.
Ces résultats permettent d’envisager l’utilisation d’invariants de cohomologie pour étudier les classes de complexité.
[http://www.ihes.fr/~seiller/]
Catégories Pas de Catégories