Institut de Mathématiques de Luminy

GROUPES DE TRAVAIL 2013
Logique et Interactions

Organisateur :
Emmanuel Beffara (tél. 04 91 26 96 35)
Lieu : IML, Bâtiment TPR2- CNRS :
Salle de Séminaires : 3ème étage (304-306).
Horaire : en règle générale le jeudi, à 14h.

jeudi 28 novembre

à 14h

Jean-Baptiste Midez
(IML, Marseille) :
Titre à préciser

Webpage : http://iml.univ-mrs.fr/ldp/membres/


jeudi 21 novembre

à 14h
Clément Aubert

Clément Aubert
(IML, Marseille) :
Logique linéaire
et classes de complexité sous-polynomiales

Webpage : http://lipn.univ-paris13.fr/~aubert/

Répétition de soutenance de thèse.
Résumé : Cette recherche en informatique théorique construit de nouveaux ponts entre logique linéaire et théorie de la complexité. Elle propose deux modèles de machines abstraites qui permettent de capturer de nouvelles classes de complexité avec la logique linéaire, les classes des problèmes efficacement parallélisables (NC et AC) et celle des problèmes solutionnables a avec peu d’espace, dans ses versions déterministes et non-déterministes (L et NL). La représentation des preuves de la logique linéaire comme réseaux de preuves est employée pour représenter efficacement le calcul parallèle des circuits booléens, y compris à profondeur constante. La seconde étude s’inspire de la géométrie de l’interaction, une délicate reconstruction de la logique linéaire à l’aide d’opérateurs d’une algèbre de von Neumann. Nous détaillons comment l’interaction d’opérateurs représentant des entiers et d’opérateurs représentant des programmes peut être reconnue nilpotente en espace logarithmique. Nous montrons ensuite comment leur itération représente un calcul effectué par des machines à pointeurs que nous définissons et que nous rattachons à d’autres modèles plus classiques. Ces deux études permettent de capturer de façon implicite de nouvelles classes de complexité, en dessous du temps polynomial.


mardi 3 octobre

à 14h
Michele Alberti

Michele Alberti
(IML, Marseille) :
Howe's method for a probabilistic λ-calculus

Webpage : http://alberti.web.cs.unibo.it


mardi 24 septembre

à 10h30
logo LDP

Matteo Acclavio
(IML, Marseille) :
An introduction to rewriting theory: homological properties of finite convergent systems

Webpage : http://iml.univ-mrs.fr/ldp/membres/


 

EL, le 27 novembre 2013