TL;DR
This paper delves into the computational complexity of reasoning with Description Logics (DLs) that incorporate defeasible reasoning, a form of nonmonotonic logic where conclusions can be retracted in light of new information. The authors extend previous work on the EL family of DLs by providing tighter complexity bounds and supporting more general forms of defeasible rules and priority relations, crucial for real-world applications like biomedical ontologies.
What Problem Does This Paper Address?
Many real-world knowledge representation tasks, particularly in domains like biomedicine or policy management, require nonmonotonic reasoning. This means that conclusions drawn from a knowledge base might need to be revised when new, more specific information becomes available. Description Logics (DLs) are a popular formalism for knowledge representation, but extending them with nonmonotonic features often leads to a significant increase in computational complexity, making practical reasoning challenging.
Previous work had established that certain DLs, like the EL family, could be extended with defeasible reasoning while keeping complexity within the polynomial hierarchy. However, these earlier results lacked matching lower complexity bounds and imposed certain syntactic restrictions. This paper aims to address these gaps by:
- Completing Complexity Characterizations: Providing matching lower bounds for previously established upper bounds.
- Relaxing Syntactic Restrictions: Supporting more general forms of defeasible rules (defeasible inclusions) and allowing for arbitrary priority relations between these rules, going beyond simple specificity.
- Extending Expressivity: Incorporating acyclic terminologies, which are common in practical knowledge bases.
Methods
The paper builds upon the framework of circumscription for DLs, a technique for nonmonotonic reasoning that prioritizes certain models. The core contributions involve:
- Reductions: The authors employ reductions from known hard problems (like propositional disjunctive logic programs and quantified boolean formulas) to prove lower bounds for reasoning tasks in their extended DL framework.
- Formal Framework Extension: They extend the existing EL¹ framework to support:
- General Defeasible Inclusions (GDIs): Allowing the left-hand side of a defeasible rule to be a compound concept, not just a concept name.
- Arbitrary Priority Relations: Moving beyond the specificity-based ordering of rules to allow for explicit, user-defined priorities.
- Acyclic Terminologies: Enabling the use of definitions like
A = CwhereCcan involve qualified existential restrictions, as long as the definitions themselves are acyclic. - Complexity Analysis: The paper systematically analyzes the computational complexity of various reasoning tasks (subsumption, instance checking, concept satisfiability) under different settings of fixed and variable concept names, and with varying levels of expressivity in the defeasible rules and terminologies. They introduce specific fragments like
LL EL+,LL2 EL+, andaLL EL+to precisely characterize these complexities.
Datasets
Not discussed in the paper. The paper focuses on theoretical complexity analysis and formal reductions rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Tightening Complexity Bounds: The paper successfully tightens the complexity bounds for reasoning in EL with defeasible inclusions, showing that even with more expressive rules and priorities, complexity often remains within the second level of the polynomial hierarchy (Σ² and Π²). This is a significant step towards practical reasoning systems.
- Impact of Fixed vs. Variable Concepts: A key insight is how the complexity changes based on whether concept names are treated as "fixed" (classical semantics) or "variable" (can be affected by nonmonotonic reasoning). Reasoning with fixed concepts (
Circfix) is generally less complex than with variable concepts (Circvar), highlighting the trade-off between expressivity and tractability. - Generalizing Priorities: The ability to handle arbitrary priority relations, not just specificity, is shown not to increase complexity beyond what's already established for simpler priority schemes. This is crucial for modeling complex real-world scenarios where explicit ordering of rules is necessary.
- Acyclic Terminologies and Tractability: The paper demonstrates that incorporating acyclic terminologies, a common feature in ontologies, can be managed while maintaining relatively low complexity, especially when combined with specific reasoning settings.
- LLfEL+ Complexity Remains Open: While significant progress is made, the exact complexity of reasoning in the
LLfEL+fragment (which allows general EL+ concepts and quantifier nesting) remains an open research question, indicating areas for future investigation.
Key Results
The paper presents a comprehensive complexity landscape for EL with defeasible inclusions. Key results include:
- Lower Bounds: Establishing matching lower bounds for reasoning in
Circvar(LL EL+)andCircfix(LL2 EL+), proving them to be Π²-hard and coNP-hard respectively. - Upper Bounds: Providing upper bounds for various fragments:
Circvar(LL EL+): Σ²-complete for subsumption and instance checking, Σ²-complete for concept satisfiability.Circfix(LL EL+): PTIME for subsumption, instance checking, and concept consistency.Circfix(LL2 EL+): coNP-complete for subsumption and instance checking, NP-complete for concept satisfiability.Circfix(aLL EL+): PSPACE-hard for subsumption checking.- Reduction Techniques: Demonstrating that reasoning with arbitrary priorities and general defeasible inclusions can be polynomially reduced to simpler forms of defeasible reasoning, simplifying the analysis.
Limitations and Future Work
- Open Complexity for LLfEL+: The exact complexity of
Circfix(LLfEL+)(which supports general EL+ concepts and quantifier nesting) is explicitly stated as an open problem. - Necessity of Quantifier Depth Bounds: It is not yet known whether the upper bounds for
Circvar(aLL EL+)(which are in Σ² and Π²) require the restriction on quantifier nesting depth. - Extending LL2 Bounds: The paper poses the question of whether the NP/coNP upper bounds for
LL2 EL+can be extended to queries beyondLL2 EL+concepts. - EL++ Constructs: The authors mention that additional features, such as those supported by the more expressive
EL++language, will be the subject of future work.
Summary updated