TL;DR
This paper revisits the well-founded semantics for hybrid MKNF knowledge bases, demonstrating that a previously proposed formalism has critical flaws. The authors introduce a new hierarchy of MKNF knowledge base classifications and a uniform characterization of various MKNF models using stable partitions, leading to updated complexity results.
What Problem Does This Paper Address?
The Semantic Web and related fields increasingly rely on combining knowledge from different sources, such as description logics (DLs) and rules. Hybrid MKNF (Minimal Knowledge and Negation as Failure) knowledge bases offer a powerful framework for this integration, aiming to reconcile open-world reasoning (DLs) with closed-world reasoning (rules). A key challenge is defining a robust and well-behaved semantics for these hybrid systems.
A prior work by Knorr et al. proposed a three-valued semantics for hybrid MKNF and claimed that if a knowledge base is consistent (has at least one three-valued model), then a unique, well-founded model exists and can be computed by an alternating fixpoint construction. This paper challenges these claims, arguing that the proposed semantics and computation method are not always correct. Specifically, they show that a consistent knowledge base might have a well-founded model that cannot be computed by the proposed method, and that some knowledge bases may have multiple, incomparable three-valued models, meaning no single "least defined" model exists in the way Knorr et al. suggested. This necessitates a re-evaluation and refinement of the semantics.
Methods
The authors introduce a novel classification of hybrid MKNF knowledge bases into a hierarchy of subclasses. They propose a uniform characterization of well-founded, two-valued, and all three-valued MKNF models. This is achieved through the concept of stable partitions, which are shown to have a one-to-one correspondence with three-valued MKNF models.
The paper also refines the alternating fixpoint construction (originally proposed by Knorr et al.) to provide a guess-and-verify approach for computing these models. This involves guessing a partition and then verifying its stability by computing alternating fixpoints and performing consistency tests. This unified approach allows for updated complexity results and the development of proof-theoretic tools for reasoning under these different semantics.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Knorr et al.'s claims are flawed: The paper provides counterexamples showing that the uniqueness and computability of well-founded MKNF models, as claimed by Knorr et al., do not always hold.
- Hierarchy of MKNF knowledge bases: The authors propose a classification of hybrid MKNF KBs into a hierarchy, suggesting that only the innermost subclass truly aligns with the intended well-founded semantics.
- Stable partitions as a unifying concept: Stable partitions offer a new, intuitive way to characterize all types of MKNF models (well-founded, two-valued, and three-valued), bridging the gap between different semantic notions.
- Refined alternating fixpoint construction: The alternating fixpoint construction is repurposed as a guess-and-verify mechanism, providing a more robust method for computing MKNF models.
- Updated complexity results: The new characterizations lead to revised complexity results for reasoning tasks in hybrid MKNF knowledge bases.
Key Results
The paper demonstrates through counterexamples that:
- A hybrid MKNF KB can have a well-founded MKNF model that is not computable by the alternating fixpoint construction proposed by Knorr et al.
- A hybrid MKNF KB can have multiple three-valued MKNF models that are incomparable in terms of undefinedness, meaning no single "least defined" model exists.
The authors introduce the concept of stable partitions and prove a one-to-one correspondence between stable partitions and three-valued MKNF models. They also establish a hierarchy of MKNF knowledge base classes (MKNF-consistent, MKNF-strongly consistent, MKNF-coherent), with MKNF-coherent KBs being the intended target of the well-founded semantics. The paper also presents new complexity results, indicating that deciding the existence of a three-valued MKNF model for a hybrid MKNF KB is in NP-complete (or PSPACE if the DL component is not decidable in polynomial time).
Limitations and Future Work
The paper is an extended abstract, so detailed proofs and extensive experimental evaluations are not included. The authors acknowledge that their work leads to a classification of hybrid MKNF knowledge bases into a hierarchy, implying that not all KBs behave as expected by the original Knorr et al. semantics. Future work would involve developing practical reasoning systems based on the stable partition characterization and exploring the implications of this hierarchy for knowledge representation and reasoning in more complex scenarios.
Summary updated