Résumé Technique : Combinaison de Propriétés pour l'Abduction d'ABox sous Sémantique de Réparation pour $\mathcal{EL}^\bot$

Énoncé du Problème

L'article traite du problème d'abduction d'ABox au sein des logiques de description (spécifiquement $\mathcal{EL}^\bot$) sous sémantique de réparation. L'abduction cherche à trouver une hypothèse (un ensemble d'assertions $\mathcal{H}$) qui, lorsqu'elle est ajoutée à une base de connaissances inconsistante $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$, rend vraie une implication manquante (observation) $\alpha$.

Dans le contexte de la sémantique de réparation, les inconsistances sont gérées en considérant des « réparations » (sous-ensembles maximaux cohérents de l'ABox). L'article se concentre sur deux sémantiques spécifiques :

1. Sémantique Brave (Brave Semantics) : $\alpha$ est impliquée si elle est vraie dans au moins une réparation.
2. Sémantique AR (All Repairs Semantics) : $\alpha$ est impliquée si elle est vraie dans toutes les réparations.

Alors que des travaux antérieurs [17] ont étudié la complexité computationnelle de l'abduction pour des propriétés désirables individuelles (par exemple, non-trivialité, restriction de signature, confinement de conflit et divers critères de minimalité), cet article étudie les combinaisons de ces propriétés. La question de recherche centrale est de savoir si exiger qu'une hypothèse satisfasse plusieurs propriétés simultanément (par exemple, être à la fois non-triviale et confinante de conflit, ou sous-minimale et à signature restreinte) entraîne une augmentation de la complexité computationnelle par rapport à la satisfaction de ces propriétés de manière isolée.

Méthodologie

Les auteurs analysent la complexité computationnelle de deux problèmes de raisonnement fondamentaux pour les combinaisons de propriétés :

1. Problème d'existence : Existe-t-il une hypothèse satisfaisant les propriétés données ?
2. Problème de vérification : Un ABox $\mathcal{H}$ donné satisfait-il les propriétés et constitue-t-il une hypothèse valide ?

L'étude couvre des combinaisons de :

• Propriétés de base :
  • Non-trivialité : L'hypothèse ne contient pas l'observation $\alpha$.
  • Restriction de signature ($\Sigma$-restreinte) : L'hypothèse n'utilise que des symboles issus d'une signature spécifiée.
  • Confinement de conflit (Conflict-confining) : L'hypothèse n'introduit pas de nouveaux conflits au-delà de ceux déjà présents dans $\mathcal{K}$.
• Critères de minimalité :
  • Sous-minimalité d'inclusion ($\subseteq$-minimalité) : Aucun sous-ensemble propre de l'hypothèse n'est une hypothèse valide.
  • Minimalité de cardinalité ($\leq$-minimalité) : Aucun hypothèse avec moins d'assertions n'est valide.
  • Minimalité de conflit ($\subseteq_c$-minimalité) : Aucune hypothèse n'introduit un ensemble de conflits strictement plus petit.

L'analyse s'appuie sur les classes de complexité standards ($\text{P}, \text{NP}, \text{coNP}, \text{DP}, \Sigma^P_2, \Pi^P_2$) et emploie des réductions à partir de problèmes connus (par exemple, la validité de QBF, l'implication/non-implication combinées) pour établir des bornes inférieures, et des algorithmes de type "deviner et vérifier" (guess-and-check) avec des appels d'oracle pour établir des bornes supérieures.

Contributions Clés et Résultats

1. Combinaisons de Propriétés de Base (Non-Minimalité)

L'article démontre que la combinaison de propriétés de base n'augmente généralement pas la complexité au-delà de la complexité la plus élevée des propriétés individuelles.

• $\Sigma$-restriction + Non-trivialité : La complexité reste $\text{NP}$-complète pour la sémantique Brave et $\Sigma^P_2$-complète pour la sémantique AR.
• Confinement de conflit + Non-trivialité / $\Sigma$-restriction : La complexité augmente à $\Sigma^P_2$-complète pour les deux sémantiques, Brave et AR. C'est un résultat notable car les hypothèses confinantes de conflit seules sont $\Sigma^P_2$-complètes pour Brave mais seulement $\text{coNP}$-complètes pour AR ; l'ajout de la non-trivialité ou de la restriction de signature élève la complexité AR pour correspondre au cas Brave.

2. Combinaisons avec la Sous-minimalité d'inclusion ($\subseteq$-minimalité)

• Sous-minimale d'inclusion + Non-trivial / $\Sigma$-restreinte : La complexité correspond à celle de la vérification des hypothèses sous-minimales d'inclusion seules ($\text{DP}$-complète pour Brave, $\Pi^P_2$-complète pour AR).
• Sous-minimale d'inclusion + Confinement de conflit :
  • Pour la sémantique Brave : $\text{DP}$-complète.
  • Pour la sémantique AR : La complexité est dans $\Pi^P_2$ et $\text{coNP}$-dure, mais la borne supérieure précise reste ouverte.

3. Combinaisons avec la Minimalité de Cardinalité ($\leq$-minimalité)

Contrairement à la sous-minimalité d'inclusion, la minimalité de cardinalité conduit souvent à une augmentation de la complexité lorsqu'elle est combinée avec d'autres propriétés, principalement parce que l'hypothèse triviale (taille 1) est souvent proscrite par la non-trivialité ou les restrictions de signature.

• $\leq$-minimale + Non-trivial / $\Sigma$-restreinte : La complexité augmente à $\text{DP}$-complète pour Brave et $\Pi^P_2$-complète pour AR.
• $\leq$-minimale + Confinement de conflit :
  • Pour la sémantique Brave : $\Pi^P_2$-complète.
  • Pour la sémantique AR : $\text{coNP}$-complète (reste inchangée par rapport au cas de la propriété unique grâce au Lemme 6, qui stipule que pour AR, l'existence implique que l'hypothèse triviale est confinante de conflit).

4. Combinaisons avec la Minimalité de Conflit ($\subseteq_c$-minimalité)

• $\subseteq_c$-minimale + Non-trivial / $\Sigma$-restreinte : La complexité est $\Pi^P_2$-complète pour les sémantiques Brave et AR.
• L'article note que l'extension de ces résultats à la minimalité de conflit de cardinalité ($\leq_c$) est difficile en raison du potentiel d'une petite hypothèse à déclencher un nombre exponentiel de nouveaux conflits, suggérant une potentielle dureté $\#\text{P}$.

Signification et Revendications

L'observation principale de l'article est que requérir des propriétés supplémentaires pour les hypothèses n'entraîne souvent pas d'augmentation de la complexité, à condition que les propriétés ne soient pas des critères de minimalité impliquant la cardinalité ou le nombre de conflits.

• Résultat principal : Pour la plupart des combinaisons de propriétés de base (non-trivialité, restriction de signature, confinement de conflit) et la sous-minimalité d'inclusion, la complexité est régie par la "plus haute" complexité parmi les propriétés individuelles impliquées.
• Exception : Les combinaisons impliquant la minimalité de cardinalité ou la minimalité de conflit entraînent fréquemment des classes de complexité plus élevées (par exemple, passer de $\text{coNP}$ à $\Pi^P_2$ ou $\text{DP}$).
• Portée : Les résultats sont spécifiques à $\mathcal{EL}^\bot$ sous les sémantiques Brave et AR. Les auteurs notent que pour des logiques plus expressives (comme $\mathcal{ALC}$), la complexité est probablement dominée par le problème d'implication lui-même (ExpTime), rendant ces distinctions d'abduction moins impactantes.
• Travaux futurs : Les auteurs identifient des lacunes ouvertes, spécifiquement la complexité précise pour les hypothèses AR confinantes de conflit et sous-minimales d'inclusion, ainsi que le paysage de complexité pour les combinaisons dans $\text{DL-Lite}$ (où ils soupçonnent que le confinement de conflit pourrait simplifier les problèmes en raison de propriétés structurelles) et sous la sémantique IAR.

L'article conclut que bien que la combinaison de propriétés soit souhaitable pour les applications pratiques (par exemple, générer des explications qui soient à la fois minimales et confinantes de conflit), cette désirabilité ne se fait pas nécessairement au prix d'une augmentation de l'intraitabilité computationnelle pour les combinaisons les plus courantes.