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 28 Mai 2002

Lois 0-1 en logique modale

par Jean-Marie Le Bars (GREYC Caen)

Les premiers résultats de lois 0-1 en logiques modales ont été obtenus pour la satisfaisabilité sur les structures de Kripke et les frames par Halpern et Kapron en 1992.

Après une présentation des logiques modales et des lois 0-1, on s'intéressera à une propriété sur les graphes orientés, la propriété de noyau. Certaines variantes de celle-ci ont déjà été utilisées comme contre-exemples aux lois 0-1 pour des fragments de la logique du second ordre. Goranko et Kapron ont montré récemment que certaines variantes étaient exprimables pour la satisfaisabilité sur les frames.

On proposera une autre variante qui permet de montrer qu'il n'y a pas de loi 0-1 pour cette logique, ce qui contredit le résultat précédemment établi par Halpern et Kapron.

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