First-Order Disjunctive Logic Programming vs Normal Logic Programming

Yi ZhouIJCAI 2015

Abstract

In the field of Answer Set Programming (ASP), the relationship between different logic fragments determines the computational power and modeling flexibility available to researchers. While it is well-established that Disjunctive Logic Programming (DLP) and Normal Logic Programming (NLP) are equally expressive in propositional logic, this paper demonstrates that this equivalence does not hold in first-order logic. By employing progression semantics and complexity theory, the study proves that first-order DLP is strictly more expressive than NLP, identifying specific subclasses where translation remains possible and highlighting the fundamental limits of "unfolding and shifting" techniques.

Introduction

Answer Set Programming (ASP) serves as a powerful framework for modeling complex search and optimization problems. In ASP, users describe the constraints and properties of a solution rather than the specific steps to achieve it. Two primary variants of ASP are Normal Logic Programming (NLP), where rules lead to a single conclusion, and Disjunctive Logic Programming (DLP), where rules allow for multiple possible conclusions (disjunctions).

Historically, researchers proved that for propositional logic—where the domain of facts is fixed and finite—any disjunctive program could be converted into a normal one. However, most practical applications of ASP utilize first-order logic, which incorporates variables to describe relationships across potentially infinite or unknown domains. This paper investigates whether the expressivity equivalence of the propositional world carries over to the first-order world.

Theoretical Framework: Progression Semantics

To analyze the limits of these logic families, the author utilizes Progression Semantics. This approach views the construction of an "answer set" as an evolutionary process, where mathematical structures develop over discrete steps. This framework allows for a rigorous comparison of how NLP and DLP handle non-deterministic choices and recursive definitions.

The paper specifically examines a common translation strategy known as unfolding and shifting:

  1. Unfolding: A process of pre-calculating rule components by substituting definitions into other rules to simplify the program structure.
  2. Shifting: A technique that converts a disjunctive rule (e.g., $A \vee B \leftarrow C$) into normal rules using negation (e.g., $A \leftarrow C, \text{not } B$).

The Expressivity Gap

The central finding of the research is that the transition from propositional to first-order logic fundamentally alters the power of the language. The author proves Theorem 1, which states that there exists a first-order disjunctive program for which no equivalent normal program exists over the same vocabulary.

The Role of Complexity and Auxiliary Predicates

A common strategy to increase the power of a logic language is the addition of "auxiliary predicates" (helper variables). However, the paper demonstrates that even with these additions, NLP cannot match the expressivity of DLP. This conclusion is rooted in complexity theory: if first-order NLP could perfectly emulate DLP, it would imply that the complexity classes $NP$ and $coNP$ are equal—a scenario widely considered impossible in computational theory. Using the "3-colorability" problem from graph theory, the author illustrates that certain properties, such as non-3-colorability, can be expressed in DLP but remain beyond the reach of standard NLP.

The Unfolding Bottleneck

The reason translation fails in the general first-order case lies in the nature of recursion and variables. In propositional logic, a program can only be "unfolded" a finite number of times before all possibilities are exhausted. In first-order logic, the presence of variables and recursive rules means the unfolding process could theoretically continue indefinitely. Consequently, any translation attempt via unfolding and shifting is inherently incomplete for general first-order programs; it may produce a sound result (where the answer sets found are valid), but it cannot guarantee the discovery of all answer sets.

Identifying "Safe" Subclasses

Despite the general impossibility of translation, the paper identifies two significant subclasses of disjunctive programs that are "NLP-definable" and can be safely translated:

  • Head-cycle-free programs: Programs where disjunctive choices do not create circular dependencies within the logic flow.
  • Choice-bounded programs: Programs where the number of non-deterministic choices made during the progression of the answer set is strictly limited.

These definitions provide a theoretical bridge for developers, indicating when they can utilize simpler, more common NLP solvers without sacrificing the integrity of their disjunctive models.

Conclusion and Future Directions

This research establishes that first-order DLP is a strictly more powerful tool than NLP, clarifying a long-standing question in computational logic. While the proposed "unfolding and shifting" method is incomplete for the general case, it remains a vital tool for specific subclasses of programs.

Future work involves developing more sophisticated heuristics for the unfolding process to maximize the effectiveness of partial translations in real-world solvers. Additionally, the author posits a conjecture that a disjunctive program is NLP-definable if and only if it can be successfully translated via unfolding and shifting. Proving this conjecture would provide the definitive boundary between these two fundamental logic families.

Summary updated

BibTeX
@inproceedings{zhou2015first,
  author = {Yi Zhou},
  title = {{First-Order Disjunctive Logic Programming vs Normal Logic Programming}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure