First-Order Indefinability of Answer Set Programs on Finite Structures

Yin Chen, Yan Zhang, Yi ZhouAAAI 2010 · DOI

Abstract

Answer Set Programming (ASP) is a powerful declarative paradigm often used for solving NP-hard problems. While its expressive power is known to reach second-order logic, the conditions under which an ASP program can be simplified into First-Order (FO) logic remain a critical area of study. This paper establishes a formal framework for proving the FO-indefinability of ASP programs on finite structures. By adapting Ehrenfeucht-Fraïssé games and introducing sufficient conditions such as the "0-1 property" and "unbounded cycles," the authors provide theoretical tools to determine the limits of ASP expressivity without exhaustive logical proofs.

1. Introduction

Answer Set Programming (ASP) has emerged as a dominant tool for solving complex combinatorial problems in fields ranging from planning to bioinformatics. While traditional ASP is propositional, modern implementations allow for variables, effectively elevating its expressive power to that of second-order logic. However, this increased power comes at the cost of computational complexity.

A fundamental question in finite model theory is whether a problem expressed in a high-level language like ASP can be "collapsed" into a simpler First-Order (FO) sentence. If such a reduction is possible, the problem is considered FO-definable. Conversely, if no such FO sentence exists, it is FO-indefinable. Proving indefinability is notoriously difficult, particularly for ASP, because its "negation as failure" semantics break many assumptions used in traditional logic. This research addresses this gap by providing the theoretical machinery to prove negative results regarding ASP's expressivity.

2. Methodology: Adapting Ehrenfeucht-Fraïssé Games

The primary tool for proving FO-indefinability is the Ehrenfeucht-Fraïssé (EF) game. In its classical form, the game involves two players—the Spoiler and the Duplicator—who select elements from two distinct mathematical structures. If the Duplicator can mirror the Spoiler's moves for $k$ rounds such that the selected elements remain isomorphic, the structures are indistinguishable by any FO sentence of quantifier rank $k$.

The authors adapt this game-theoretic approach to the ASP context. They establish that an ASP program is FO-indefinable if and only if, for any integer $k$, there exist two structures where one satisfies the program (i.e., has an answer set) and the other does not, yet the Duplicator possesses a winning strategy for the $k$-round EF game. This result, formalized in Theorem 2, provides a bridge between ASP semantics and FO logic.

3. Simplifying Proofs: The 0-1 Property and Unbounded Cycles

Constructing winning strategies for EF games is often technically exhausting. To streamline this process, the authors introduce several "shortcuts" based on structural properties of programs and their data:

3.1 The 0-1 Property

The authors define a class of 0-1 programs. In these programs, the resulting intentional predicates (the relations defined by the program) are either completely empty (0) or contain every possible tuple (1) across the domain. This property simplifies the analysis of how programs behave across different structures.

3.2 Gaifman Graphs and Unbounded Cycles

To analyze the structural relationships within data, the paper utilizes Gaifman graphs. These graphs represent elements as nodes and their relations as edges. A key contribution of the paper is Theorem 4, which links indefinability to the presence of "unbounded cycles" or paths. If a 0-1 program can recognize or operate on cycles of arbitrary length, it is likely FO-indefinable. This allows researchers to prove complexity results by examining the program's behavior on specific graph structures rather than playing out the full EF game.

4. Case Studies

The paper validates its framework using several benchmark computational problems:

  • Hamiltonian Cycle ($\Pi_{HC}$): The authors provide a rigorous formal proof that the standard ASP program for finding Hamiltonian cycles is FO-indefinable. While this result was intuitively expected given the problem's NP-completeness, the paper provides the first rigorous logical machinery to confirm it.
  • Reachability and Transitive Closure: Using programs like $\Pi_{RChecking}$ and $\Pi_{TCovered}$, the authors demonstrate how the 0-1 property and the unbounded cycles theorem can be applied to simpler, polynomial-time problems that nonetheless exceed the expressive power of FO logic.

5. Conclusion and Future Work

This research provides a robust theoretical foundation for understanding the limits of ASP. By establishing Theorem 2 and Theorem 4, the authors offer both a necessary condition (via EF games) and a practical sufficient condition (via unbounded cycles) for FO-indefinability.

However, limitations remain. The most powerful shortcut theorems are currently restricted to 0-1 programs. While many common ASP programs fit this category, extending these results to more general programs is a clear path for future research. Additionally, while this paper focuses on negative results, identifying subclasses of ASP that are guaranteed to be FO-definable could lead to significant breakthroughs in query optimization and evaluation efficiency.

Summary updated

BibTeX
@inproceedings{chen2010first,
  author = {Yin Chen and Yan Zhang and Yi Zhou},
  title = {{First-Order Indefinability of Answer Set Programs on Finite Structures}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7589},
}
Figure