TL;DR
This paper introduces DLP(S), an extension of Answer Set Programming (ASP) that allows for the representation of sets, significantly boosting expressive power for problems like ontology reasoning. They propose two novel methods for handling these set-based programs: a translation to ASP with function symbols and a grounding approach using existential rules, demonstrating their practical feasibility and outperforming naive approaches.
What Problem Does This Paper Address?
Answer Set Programming (ASP) is a powerful declarative programming paradigm, but its expressiveness is limited, particularly for problems involving complex data structures. While extensions exist for function symbols and lists, incorporating sets of constants offers a more intuitive modeling style and has been shown to increase expressive power in related formalisms like Datalog. However, the theoretical properties and practical implementation of ASP with sets (DLP(S)) remained largely unexplored, with existing ASP solvers struggling with the computational challenges posed by set representations. This paper aims to bridge this gap by formally defining DLP(S), analyzing its reasoning complexity, and developing efficient implementation strategies.
Methods
The authors propose two primary methods for handling DLP(S) programs:
- Translation to ASP with Function Symbols (DLPf): They introduce a semantics-preserving translation of DLP(S) rules into DLPf rules. This involves encoding sets using a special empty set constant and a function symbol for union, along with auxiliary predicates to manage singleton unions and equality checks. This approach leverages existing techniques for handling function symbols in ASP solvers, particularly those with lazy grounding capabilities.
- Grounding with Existential Rules: An alternative approach is presented that grounds DLP(S) programs using existential rules. This method simulates set operations by translating DLP(S) rules into a stratified set of existential rules. The "stratified chase" procedure is then used to infer ground facts, which are subsequently converted back into DLP(S) rules. This approach aims to leverage specialized existential rule reasoners.
Datasets
The evaluation uses eight ontologies from the Oxford Ontology Repository. These ontologies are pre-processed to conform to the description logic Horn-ALC and then transformed into facts for classification tasks. The paper also mentions that the full datasets and source code are available in an online repository.
Key Insights and Ideas
- Sets Significantly Boost Expressive Power: The paper demonstrates that incorporating sets into ASP (DLP(S)) unlocks the ability to model problems that are intractable for plain ASP, such as complex ontological reasoning.
- Decidability is Preserved (with a Caveat): While DLP(S) reasoning is decidable, its complexity is high (CONEXPTIMENP-complete), even for data complexity. This highlights the trade-off between expressiveness and computational cost.
- Lazy Grounding is Crucial: Traditional ASP grounders struggle with the non-stratified nature of the translated DLPf programs. Lazy grounding approaches, which interleave grounding and solving, are shown to be essential for handling these programs effectively.
- Existential Rules Offer a Viable Alternative: The existential rule grounding approach provides another practical method for reasoning with DLP(S), demonstrating competitive performance with native set implementations.
- Native Set Implementations are Competitive: The DLV-complex system, which natively supports set terms, performs well on the evaluated tasks, suggesting that dedicated implementations are also a strong option.
Key Results
- Formalization of DLP(S): The paper formally defines DLP(S) and establishes its reasoning complexity.
- Two Novel Implementation Methods: Two distinct methods for implementing DLP(S) reasoning are presented and evaluated: translation to DLPf with lazy grounding and grounding via existential rules.
- Competitive Performance: The proposed existential rule grounding approach (EXRULES) and the native DLV-complex system (DLVCOMP) showed competitive performance on tasks involving ontological reasoning, including classification, transitive reduction, and computing maximal antichains.
- Lazy Grounding Underperformance: The lazy grounding approach (LAZY) using Alpha was surprisingly less effective, often timing out on tasks that the other methods could handle. This suggests potential issues with the specific implementation or heuristics used.
- Real-World Applicability: The evaluation on real-world ontologies demonstrates the practical utility of DLP(S) for solving problems beyond the scope of traditional ASP.
Limitations and Future Work
- High Computational Complexity: The CONEXPTIMENP-complete complexity of DLP(S) reasoning, even for data complexity, remains a significant challenge.
- Lazy Grounding Performance: The observed underperformance of the lazy grounding approach warrants further investigation and optimization.
- Native Integration: The authors suggest exploring native integration of set types within ASP solvers (e.g., via clingo's @-terms or DLV's external atoms) as an alternative to translation.
- Broader Applications: Future work could explore the use of set terms in ASP for other areas like abstract argumentation and for native integration with description logics.
- Further Optimization: The paper notes that optimizations in the translation process (e.g., using
get_suandsuinstead ofget_uandu) could be beneficial but were omitted for formal simplicity.
Summary updated