Une augmentation brutale de la complexité de représentation, du coût computationnel ou du nombre de modèles qui se produit lorsqu'un fragment logique auparavant bien maîtrisé est étendu par des opérateurs, des constructions ou des assouplissements syntaxiques supplémentaires.

Principe

Les fragments sont des sous-ensembles d'un langage logique choisis pour des méta-propriétés souhaitables (décidabilité, complexité faible). Étendre un fragment en ajoutant des fonctionnalités (alternance de quantificateurs, clôture transitive, comptage, relations d'arité supérieure) peut rompre ces garanties, provoquant une explosion dans la vérification de satisfaisabilité, la taille des modèles ou la complexité du raisonnement.

Démonstration

Partir d'un fragment gardé qui admet des procédures de décision à complexité prévisible ; l'ajout de relations binaires transitives non restreintes ou de certains quantificateurs de comptage peut faire passer la satisfaisabilité d'une classe polynomiale/décidable à une classe intraitable ou indécidable dans ce fragment. Un exemple illustratif est une extension introduisant de nombreuses dépendances interactives et exponentiellement de nombreux témoins.

Mauvaise application

Supposer qu'une extension syntaxique modeste préserve les propriétés du fragment original sans preuve, ou imputer la lenteur d'un outil à l'explosion du fragment alors que le problème réel est un mauvais ancrage ou de mauvaises options d'encodage.

Conséquence

La connaissance de l'explosion de fragment oriente la conception des langages, incitant soit à une discipline de fragment plus stricte, à des restrictions de fonctionnalités, soit à l'utilisation d'approximation et de modularisation ; elle motive la recherche de frontières serrées de tractabilité.

Inversion

Si chaque extension d'un fragment conservait son comportement maîtrisé, les concepteurs pourraient ajouter librement des fonctionnalités expressives sans compromettre la décidabilité ou les performances, simplifiant grandement l'évolution des langages et l'interopérabilité des outils.

Limite

Concerne des fragments spécifiques et les opérateurs particuliers ajoutés ; elle exclut des affirmations générales sur des familles entières de logiques et dépend d'interactions syntaxiques et sémantiques fines entre les constructeurs.

Tension sémantique

S'oppose au désir d'expressivité : les utilisateurs souhaitent des langages plus riches pour exprimer succinctement des concepts tandis que les théoriciens veulent des fragments au comportement prévisible ; la tension consiste à choisir quels compromis accepter.

Synthèse

L'Explosion de Fragment décrit comment des extensions modestes à un fragment logique soigneusement choisi peuvent soudainement détruire ses propriétés computationnelles favorables, produisant des sauts de complexité et de multiplicité de modèles qui forcent à réévaluer les fonctionnalités du langage et les pratiques d'ingénierie.