Complexité, Modèles Finis et Bases de Données

Mardi 2 Février et Mercredi 3 Février à Jussieu - programme provisoire

Mardi 2 Février - salle AFORIA 46-0 2eme Etage

Chair: Etienne Grandjean

1. 9h-10h Patrick Cegielski, Subsequence Matching. (avec L. Boasson, I. Guessarian et Y. Matiyasevich)
2. 10h-11h Michel de Rougemont, Définissabilité et compression. (avec F. Afrati)
3. 11h30-12h10 Nicole Schweikardt, On a logical characterisation of NTIME(n). (avec C. Lautemann et T. Schwentick)

Déjeuner

1. 14h-14h30 Jean-Yves Marion, Complexité des algorithmes définis par des systèmes de réecriture avec interprétation polynomiale.
2. 14h30-15h Laurent Juban, Sur la complexité du calcul de la base de Hilbert d'un système diophantien linéaire. (avec M. Hermann, P.Kolaitis)
3. 15h-15h30 Arnaud Durand, Sur la complexité du problème de reconnaisance de la base de Hilbert d'un système diophantien linéaire. (avec M. Hermann, L. Juban)
4. 16h-16h30 Natacha Portier, Le problème des grandes puissances et celui des grandes racines.
5. 16h30-17h Yassine Hachaichi, Logic for unambiguous context free languages.
6. 17h-17h20 Caroline Fontaine, Highly Nonlinear Balanced Boolean Functions.

Chair: Michel de Rougemont

1. 9h-10h Bruno Courcelle, Graphes uniformement creux et quantifications sur les arcs en logique MS.
2. 10h-11h Erich Graedel, Datalog LITE: Temporal versus deductive reasoning in verification. (avec G. Gottlob et H. Veith)
3. 11h30-12h30 Leonid Libkin, Embedded finite models and constraint databases.

Déjeuner
Chair: Bruno Courcelle

1. 14h-15h Stéphane Grumbach, Complexity of spatial queries.
2. 15h-15h30 David Gross, Estimateurs pour les bases de données spatiales.
3. 16h-16h45 Alexandre Dikovsky, Expansion monotone des mises a jour de bases de données logiques.
4. 16h45-17h15 Frédéric Magniez, Approximate testing with relative error.