TLDR: This research paper compares four non-minimal semantics for disjunction in Answer Set Programming (ASP): Justified Models, Strongly Supported Models, Forks, and Determining Inference (DI) semantics. It reveals that Forks, Justified Models, and a relaxed version of DI semantics effectively coincide, forming a unified approach that is a superset of stable models and stronger than Strongly Supported Models. This common semantics helps restore model existence and maintains computational efficiency for disjunctive ASP programs.
Answer Set Programming (ASP) is a powerful tool for knowledge representation and problem-solving, largely due to its expressive language and declarative semantics based on ‘stable models’. While stable models are fundamental, their application to disjunction (the ‘or’ operator) in logic programs introduces complexities. Traditionally, stable models for disjunctive programs rely on a principle of ‘model minimality’, which can lead to challenges such as the absence of a direct derivation method and increased computational complexity.
This research paper delves into four alternative semantics for disjunction in ASP that move beyond the strict principle of model minimality. These approaches offer different perspectives on how disjunction can be interpreted, aiming to address some of the limitations encountered with stable models.
Also Read:
- Optimizing Answer Set Programming with Automated Hybrid Grounding
- Advancing Constraint Logic Programming: A Unified Approach to Negation with Semirings
The Four Approaches Explored:
The paper examines four distinct non-minimal semantics:
- Justified Models: Introduced by Cabalar and MuËœniz, this approach provides a definition of explanations for stable models, often resulting in more justified models than stable models for disjunctive programs.
- Strongly Supported Models: Developed by Doherty and Szalas, this semantics treats disjunctions more akin to classical logic.
- Forks: Proposed by Aguado et al., forks introduce a new disjunction connective with a unique formal semantics based on denotations.
- Determining Inference (DI) Semantics: From Shen and Eiter, this approach also introduces a new disjunction operator and is based on the idea of a ‘head selection function’ that non-deterministically chooses an atom in a disjunction.
A significant finding of the paper is that three of these approaches—Forks, Justified Models, and a reasonable relaxation of the DI semantics—actually coincide. This convergence suggests a common underlying understanding of disjunction in ASP when the minimality principle is relaxed. This unified semantics consistently provides a superset of the stable models of a program and is strictly stronger than the fourth approach, Strongly Supported Models.
The implications of this convergence are noteworthy. By adopting this common semantics, disjunctive programs that might otherwise lack stable models can regain ‘coherence’ (the existence of a stable model). Furthermore, the computational complexity for determining the existence of a model under this unified semantics remains within the NP-complete class, which is a desirable property for practical applications.
This research provides a clearer landscape of non-minimal semantics for disjunction in ASP, highlighting a significant area of agreement among different theoretical constructs. It opens avenues for future work, including exploring other alternatives like replacing disjunctions with choice rules and further understanding their relationship to these established semantics.
For more in-depth details, you can access the full research paper here.
