Introduction
Resilient Logic Programs (RLPs) represent a significant advancement in hybrid reasoning, bridging the gap between the "closed-world" assumptions of Answer Set Programming (ASP) and the "open-world" flexibility of ontologies. This framework addresses the need for solutions that remain valid across all possible environmental scenarios defined by an ontology—a property termed "resilience."
The Challenge of Hybrid Reasoning
Knowledge Representation (KR) traditionally utilizes rule-based languages like ASP for reasoning with known facts and defaults, while ontologies (e.g., Description Logics) handle incomplete information and anonymous objects. Combining these into Hybrid Knowledge Bases has historically led to two extremes:
- World-centric: Rules only need to be consistent with a single possible model of the ontology, which is often too weak for robust planning.
- Entailment-centric: Rules only see what is logically certain (true in all models), which is often too restrictive as it ignores the specific details of individual possibilities.
RLPs fill this gap by ensuring a solution can "respond" to any valid scenario described by the environment. For example, in network design, a resilient solution ensures connectivity regardless of which specific node fails, where the failure is an environmental scenario defined by the ontology.
Methodology
RLPs categorize predicates into three distinct types to manage this "negotiation" between rules and environment:
- Output Predicates: The decisions controlled by the system (e.g., which edges to build in a graph).
- Open-world Predicates: Factors controlled by the environment or ontology (e.g., which node fails).
- Response Predicates: Internal logic that "reacts" to the environment to justify the solution (e.g., calculating reachability after a failure).
A solution is considered a resilient answer set if, for every possible model of the ontology, there exists a way to assign the response predicates such that the program's rules are satisfied. To ensure decidability, the authors introduce Relaxed Safeness, a technique that leverages ontology-defined bounds to handle open-world objects within finite rules.
Complexity and Results
The RLP framework naturally captures $\exists\forall\exists$ quantification structures, placing it at the $\Sigma^P_3$ level of the polynomial hierarchy. This makes RLPs more expressive than most existing hybrid ASP languages. The authors established rigorous complexity bounds for various Description Logics (DLs), as summarized in the following table:
As shown in Figure 1, for expressive ontologies like $\mathcal{ALCHOIQ}$, the combined complexity can reach NEXPTIME levels. However, for many common DLs, the data complexity remains $\Sigma^P_3$-complete, aligning with the framework's inherent $\exists\forall\exists$ structure. Crucially, the authors demonstrate that a significant fragment of RLPs can be compiled into standard disjunctive ASP, allowing the use of highly-optimized solvers like Clingo or DLV.
Conclusion and Future Work
While RLPs offer high expressivity and a path toward practical implementation, their computational cost ($\Sigma^P_3$ or NEXPTIME) remains a challenge for large-scale problems. Current restrictions on default negation in front of response predicates are necessary for ASP translation but limit some modeling flexibility. Future research will explore "stratified negation" to potentially lower complexity and aim to benchmark these systems in real-world configuration and planning scenarios.
Summary updated