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