Splitting Answer Set Programs with Respect to Intensionality Statements

Jorge Fandinno, Yuliya LierlerAAAI 2023 · DOI

Abstract

In Answer Set Programming (ASP), splitting is a fundamental technique for decomposing large programs into smaller, manageable subprograms to facilitate computation and verification. However, traditional splitting theorems often fail when dependencies appear circular at the predicate level, even if they are stratified in practice (e.g., across time steps in planning). This paper introduces a generalized splitting framework that utilizes "intensionality statements" and contextual awareness to provide a more granular dependency analysis. By distinguishing between different conditions under which a predicate is defined, the authors provide a mathematical foundation for splitting iterative programs and meta-programs that were previously considered inseparable.

Introduction

Answer Set Programming (ASP) has become a leading paradigm for solving knowledge-intensive search problems. As programs grow in complexity, the ability to "split" a program—breaking it into a sequence of subprograms where the results of one serve as the input for the next—becomes crucial. Splitting allows for modular program development, simplified correctness proofs, and more efficient computation of stable models.

Historically, splitting theorems have relied on a dependency graph constructed at the predicate level. If a rule for predicate $A$ mentions predicate $B$ in its body, $A$ is said to depend on $B$. If $B$ also depends on $A$, they form a cycle and must be computed together. While effective for simple programs, this approach is often too coarse for real-world applications like iterative planning or meta-programming, where the specific arguments of a predicate determine its role in the program's logic.

The Problem: Coarse Dependencies

The primary limitation of standard splitting is its monolithic view of predicates. Consider a blocks-world planning problem where the predicate on(B, L, T) represents a block $B$ being at location $L$ at time $T$. A rule might define on(T+1) based on the state of on(T). To a standard splitting theorem, the predicate on depends on itself, creating a circular dependency that prevents the program from being split by time steps.

This lack of granularity forces solvers and developers to treat logically distinct stages of a process as a single, inseparable unit. This is particularly problematic in meta-programming, where a single predicate (like holds/1) might be used to represent the truth of many different underlying concepts, leading to a dense, un-splittable dependency graph.

Methods: Intensionality and Context

The authors propose a generalization of the Splitting Theorem by introducing three key components:

1. Intensionality Statements ($\lambda$)

Rather than labeling an entire predicate as either "defined" (intensional) or "input" (extensional), the authors introduce intensionality statements. These are first-order formulas that specify the conditions under which a predicate is considered intensional. For example, on(B, L, T) can be defined as extensional when $T=0$ (the initial state) and intensional when $T > 0$ (states derived via rules). This allows the framework to treat different instances of the same predicate differently based on their arguments.

2. Contextual Awareness ($\Psi$)

The framework incorporates a "context" or "approximator" ($\Psi$), which is a set of known facts or logical properties about the program. This context is used to evaluate whether a dependency between two predicates is actually possible. If the context proves that the conditions required to trigger a specific rule can never be met, the corresponding edge in the dependency graph is pruned.

3. Refined Dependency Graph

By combining intensionality statements with contextual pruning, the authors construct a refined dependency graph. The vertices in this graph are not just predicates, but pairs of predicates and their associated intensionality statements. This higher-resolution graph can reveal a stratified structure in programs that appear circular under traditional analysis.

Key Results

The primary theoretical contribution is a new Splitting Theorem (Theorem 2) applicable to arbitrary first-order theories. This theorem proves that under the refined dependency conditions, the stable models of the global program are exactly the combinations of the stable models of the resulting subprograms.

Implications for Iterative Solving

This work provides the first formal justification for the "iterative solving" techniques used by modern ASP solvers like clingo. It mathematically validates the practice of solving for time $T$ and using those results as fixed facts for time $T+1$, even when the underlying rules use the same predicate symbols across all time steps.

Support for Meta-Programming

The framework also enables the splitting of meta-programs. In meta-programming, rules are often treated as data, and a universal predicate like holds/1 is used to evaluate them. Standard theorems cannot split such programs because every rule appears to depend on every other rule through the shared holds predicate. The new theorem allows developers to split these programs by defining intensionality based on the structure of the terms passed to the meta-predicate.

Limitations and Future Work

While theoretically robust, the proposed method faces a significant practical challenge: undecidability. Determining whether an edge exists in the refined dependency graph requires proving that certain first-order formulas are unsatisfiable, a problem that is undecidable in the general case.

To bridge the gap between theory and practice, the authors suggest that future research should focus on integrating automated first-order theorem provers (such as Vampire) into the ASP workflow. Such tools could help programmers automatically verify if their programs satisfy the conditions for splitting, potentially leading to a new generation of highly modular and efficient ASP development tools.

Summary updated

BibTeX
@inproceedings{fandinno2023splitting,
  author = {Jorge Fandinno and Yuliya Lierler},
  title = {{Splitting Answer Set Programs with Respect to Intensionality Statements}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i5.25780},
}
Figure