Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 6 Novembre 2012

"Vers une caractérisation des requêtes faciles du premier ordre existentiel" (trois petites dichotomies pour les requêtes du premier ordre existentiel)

par Johann Brault-Baron (GREYC, Caen)

À quoi reconnaît-on une question difficile ? C’est la question que l’on se pose dans le cadre des problèmes exprimés dans la logique existentielle du premier ordre : on cherche à mettre en rapport la forme d’un énoncé logique (sa formulation) et la complexité du problème associé, que l’on appelle aussi requête.

Un premier résultat a été établi (partiellement) par G. Bagan qui énonce que, en ce qui concerne le fragment des requêtes conjonctives, la classe bien connue des requêtes dites acycliques caractérise le temps linéaire (pour ce fragment).

On fournit un résultat similaire (mais dissymétrique) pour la classe duale de la classe des requêtes conjonctives.

Enfin, on unifie ces deux résultats dans une caractérisation qui ouvre la possibilité d’une caractérisation des requêtes du premier ordre existentiel décidables en temps linéaire.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr