|
|
Vendredi 28 Mars
Heure: |
10:00 - 12:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Interaction Graphs and Complexity |
Description: |
Thomas Seiller We obtained, with C. Aubert, new characterizations of complexity classes coNL and L using methods inspired from Girard's hyperfinite Geometry of Interaction (GoI). These characterizations had some drawbacks, among which: - it used complicated tools from operator theory; - it was not related to the interpretation of logic in the Geometry of Interaction construction;
This work revisits these previous results by using Interaction Graphs, a combinatorial GoI construction developed during my thesis that simplifies, unifies and generalizes Girard's GoI constructions. This change of perspective allows for a number of improvements, namely: - the obtention of simplified characterizations of the classes coNL and L; - the obtention of new characterizations, e.g. Regular languages, NL; - it relates the method to the reconstruction of logic in Interaction Graphs (hence in GoI); - it offers new ways to obtain characterizations of other classe. |
|
|