Une borne supérieure sur la classe de propriétés ou de structures qu'un langage logique ou un fragment peut définir ou distinguer dans un cadre syntaxique ou sémantique donné ; l'étendue maximale d'expressivité disponible sans changer l'appareil formel.

Principe

Les plafonds proviennent de la combinaison des règles de formation syntaxiques, des quantificateurs et opérateurs disponibles et des invariants sémantiques : ils se caractérisent souvent par des moyens algébriques ou ludiques (par exemple via des jeux d'Ehrenfeucht-Fraïssé, des variétés algébriques ou des correspondances avec des automates).

Démonstration

Sur les mots finis, la logique monadique du second ordre (MSO) capture exactement les langages réguliers — cette caractérisation est un plafond d'expressivité pour MSO sur mots : aucun langage non régulier n'est définissable dans MSO[<] sur mots finis. De même, la logique du premier ordre avec ordre correspond aux langages sans étoile (apériodiques), établissant un plafond pour FO[<].

Mauvaise application

Affirmer qu'un plafond empêche toute approximation utile ou description partielle ; un plafond ne dit qu'une non-définissabilité dans le langage donné, pas l'impossibilité de caractérisations plus faibles ou probabilistes hors de ce cadre.

Conséquence

La connaissance d'un plafond d'expressivité permet de classifier les propriétés en définissables et non définissables et oriente le choix de logiques plus fortes ou de restrictions alternatives sur les modèles ; elle soutient les preuves de complétude et d'inexpressibilité et relie la logique aux automates et aux caractérisations algébriques.

Inversion

Étendre le langage (ajout de fonctionnalités du second ordre, de prédicats d'arité supérieure, du comptage ou d'opérateurs à point fixe) peut élever ou supprimer le plafond de sorte que des propriétés auparavant non définissables deviennent définissables ; inversement, démontrer un plafond pour une logique très expressive révèle des limites profondes liées à des invariants sémantiques.

Limite

Un plafond est évalué par rapport à une logique concrète, une signature et une classe de structures ; il ne prétend pas à l'impossibilité dans tous les formalismes et exclut les questions de concision (une propriété peut être définissable mais demander des formules peu maniables).

Tension sémantique

Le plafond interagit avec les notions de concision et de complexité : une propriété peut être sous le plafond (définissable) mais difficilement calculable depuis sa définition, ou au-dessus tout en étant approximable par des formules capturant de larges fragments de son comportement ; classer des propriétés par rapport à un plafond implique des compromis qualitatifs et quantitatifs.

Synthèse

Un plafond d'expressivité est la frontière maximale formelle de ce que le langage choisi peut définir : il est déterminé par des contraintes syntaxiques et des invariants sémantiques, souvent saisi par des jeux ou des correspondances algébriques, et indique s'il faut renforcer le langage ou modifier les hypothèses sur les modèles pour aller au-delà.