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 3 Novembre 1998

Lois 0-1 en logique

par Jean-Marie Le Bars (GREYC)

Lorsque la proportion de graphes a n sommets qui sont modeles d'une propriete P a une limite quand n tends vers l'infini, cette limite est appelee probabilite asymptotique de P.

Une logique L admet une loi 0-1 quand toute propriete P exprimable dans L a une probabilite asymptotique egale a 0 ou 1.

La logique du premier ordre admet une loi 0-1 contrairement a la logique existentielle du second ordre. Cependant certains fragments de celle-ci verifient une loi 0-1.

Nous verrons qu'une variante de la propriete de noyau, propriete NP-complete exprimable avec seulement deux variables du premier ordre, permet de caracteriser les fragments pour lesquels la loi 0-1 n'est pas verifiee.

Ce resultat etait tout a fait inattendu car il enfreint une correspondance precedemment etablie par les chercheurs de ce domaine entre decidabilite et lois 0-1.

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