Abstract FR:

La théorie des modèles finis est devenue un enjeu important de l'informatique. Les probabilités y jouent un rôle central, comme objet d'étude et comme méthode de preuve. En effet, elles conduisent aux notions de loi 0-1 et de convergence et autorisent des preuves d'existence particulièrement concises. Nous répondons à une question de Kolaitis et Vardi en donnant deux preuves finitistes de la loi 0-1 pour les énoncés de Bernays-Schönfinkel et Ackermann quantifiés existentiellement au second ordre. Nous établissons aussi la conjecture de ces auteurs sur l'incomparabilité du pouvoir d'expression de ces deux langages. Nous montrons que le problème de la frontière des lois 0-1 dans la logique du second ordre est intéressant. Nous formulons une conjecture donnant la position de cette frontière, et la prouvons en partie pour le deuxième niveau de la hiérarchie du second ordre. Nous fournissons aussi le tableau complet des lois 0-1 et de convergence de l'ensemble des propriétés monotones dans les graphes aléatoires pour la classe des probabilités d'arêtes la plus étudiée d'un point de vue logique. Nos résultats montrent que ces propriétés sont sensibles au double saut découvert par Erdös et Rényi, mais insensibles à la curieuse dichotomie rationnel / irrationnel obtenue par Shelah et Spencer pour la logique du premier ordre. Nous ouvrons ainsi l'étude des phénomènes de convergence de langages préservés par extension, comme DATALOG, pour des structures aléatoires peu denses, susceptibles de rendre compte de situations concrètes en informatique.