Polynomially Bounded Logic Programs with Function Symbols: A New Decidable

Vernon Asuncion, Yan Zhang, Heng ZhangAAAI 2017 · DOI

Introduction

In the field of Answer Set Programming (ASP), a dominant paradigm for solving complex combinatorial problems, the process typically begins with "grounding." This step involves replacing all variables in a logic program with every possible constant to create a propositional version that solvers can process. However, the introduction of function symbols (e.g., next(X) or f(X)) introduces a significant challenge: the potential for infinite groundings. A simple recursive rule can theoretically generate an endless sequence of terms—f(a), f(f(a)), f(f(f(a))), and so on—making the program impossible to solve with standard computational tools.

Identifying which programs will eventually settle into a finite set of facts (finitely groundable) is an undecidable problem. Consequently, researchers focus on defining "decidable classes"—subsets of programs that can be mathematically proven to be safe for grounding. This paper introduces POLY-bounded programs, a new, broader class of logic programs that remain finitely groundable by accounting for disjunctions, negations, and constraints more effectively than previous methods.

The Problem: Beyond Existing Safety Nets

Previous attempts to define safe classes, such as GMT-bounded or size-restricted programs, often proved too restrictive. They frequently failed to recognize the safety of programs that use negative information or constraints to prune infinite growth. For example, a photo gallery system might allow members to view images but impose a hard limit on the number of views. While the recursive structure might look infinite on the surface, the constraint ensures the process terminates. Existing safety checks often missed these nuances, labeling safe programs as potentially infinite.

Methodology: The Progression-Based Procedure

The authors propose a progression-based analysis to estimate the "upper bound" of a program's stable models. This approach determines if the depth of terms generated by a program will eventually stabilize. The method follows two primary steps:

  1. Deriving a Lower Bound ($K^\infty$): The system identifies facts that are guaranteed to be true or false based on the program's structure. This involves a "shifting" transformation ($\Pi^{DEF}$) that normalizes complex disjunctive rules, making them easier to analyze.
  2. Defining the Upper Bound ($\Gamma^\infty$): By leveraging the knowledge of what is definitely false, the procedure "prunes" the program. If a rule's execution depends on a fact already proven false, that rule is considered "defeated" and is removed from the potential paths toward infinite growth.

Crucially, a program is classified as POLY-bounded if the maximum depth of its terms ceases to grow after a specific number of iterations. This iteration limit is defined by a polynomial $I(\Pi) = N + N^3$, where $N$ is a value derived from the number of rules and the arities (the number of arguments) of the predicates and functions.

Key Insights

The $N^3$ Factor

The choice of a cubic polynomial for the iteration bound is a central contribution of the paper. This bound accounts for the complex ways arguments can be transposed between predicates and how terms can be simplified or "undone" through cycles within the program logic. It provides a mathematically rigorous stopping point to prove safety.

Handling Negation and Constraints

Unlike many previous methods that struggled with negative information, POLY-boundedness explicitly tracks what cannot be true. This allows the framework to prove that certain recursive loops, which appear infinite, are actually blocked by constraints or negations in practice.

Strict Containment

The authors demonstrate that POLY-boundedness is a "proper superclass." This means it successfully captures every program previously deemed safe by GMT-bounded or size-restricted definitions, while also identifying a significant number of new, valid programs that were previously excluded.

Results and Complexity

The paper establishes several key theoretical results:

  • Decidability: Any program identified as POLY-bounded is guaranteed to have a finite grounding.
  • Complexity: Determining whether a program is POLY-bounded is EXPTIME-complete. While computationally expensive, this complexity is the necessary trade-off for a significantly more expressive and intelligent safety check.
  • Functional Normal Form: The authors prove that programs can be converted into a "functional normal form" (limiting term depth to 1) without affecting the ability to verify POLY-boundedness.

Conclusion and Future Work

While the EXPTIME-complete nature of the check suggests potential overhead for very large programs, it offers a powerful new tool for ASP developers. The next phase of this research involves integrating the POLY-bounded check into mainstream ASP grounders, such as Gringo. This integration will allow researchers to test the practical performance of the check against real-world benchmarks, potentially expanding the range of problems that can be solved using logic programming with function symbols.

Summary updated

BibTeX
@inproceedings{asuncion2017polynomially,
  author = {Vernon Asuncion and Yan Zhang and Heng Zhang},
  title = {{Polynomially Bounded Logic Programs with Function Symbols: A New Decidable}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10669},
}
Figure