Grounding for Model Expansion in k-Guarded Formulas with Inductive Definitions

Murray Patterson, Yongmei Liu, Eugenia Ternovska, Arvind GuptaIJCAI 2007

Abstract

Model Expansion (MX) is a powerful framework for solving combinatorial problems by separating problem logic from instance data. However, the grounding step—translating logic into propositional formulas—often leads to an exponential explosion in size. This paper introduces an efficient grounding algorithm for $k$-guarded formulas, a fragment of first-order logic related to low treewidth. By utilizing "extended relations" and a novel relational algebra, the authors demonstrate that grounding can be performed in polynomial time $O(\ell \cdot n^k)$. Furthermore, the algorithm supports inductive definitions (FO(ID)), enabling the modeling of recursive properties like reachability without sacrificing efficiency.

Introduction: The Grounding Bottleneck

In Artificial Intelligence, complex combinatorial problems such as scheduling or graph coloring are frequently solved by describing them in high-level logic and employing a SAT solver. The "Model Expansion" (MX) framework facilitates this by separating the logical rules (the problem description) from the specific instance data. A critical step in this pipeline is grounding: the translation of high-level descriptions into a massive collection of propositional statements.

Traditionally, grounding is a major bottleneck. For a problem with $n$ elements and $v$ variables, naive grounding can produce formulas of size $O(n^v)$, which becomes computationally infeasible even for small datasets. This research seeks a "sweet spot"—a logic fragment expressive enough for NP-hard problems but structured enough to allow efficient, polynomial-time grounding.

Methods: Guarded Logic and Extended Relations

The authors focus on the Guarded Fragment of first-order logic. In this fragment, every quantified variable must be "guarded" by an atom (a predicate). For instance, instead of a general quantification "for all $x, y$", the logic requires "for all $x, y$ such that $Edge(x, y)$". This structural constraint is closely linked to bounded treewidth, a property that often makes hard graph problems tractable.

To process these formulas, the authors introduce Extended Relations. Unlike standard database relations that only store "True" tuples, extended relations store tuples alongside propositional formulas ($\psi$) that represent the conditions under which those tuples are satisfied.

An example of an extended relation where tuples are associated with propositional formulas.

The core of the approach is the IGnd Algorithm, which treats grounding as a form of database query evaluation. It uses a specialized relational algebra (including join, projection, and union operations) designed for extended relations. To prevent formula growth, the algorithm introduces new propositional symbols to "name" intermediate sub-formulas, effectively taming the exponential explosion. This process can be visualized as a hierarchical decomposition of the logic formula.

The hierarchical decomposition of a complex formula during the grounding process.

Handling Inductive Definitions

A significant contribution of this work is the extension of the algorithm to handle FO(ID)—first-order logic with inductive definitions. This allows for the representation of recursive concepts, such as "reachability" in a graph, which are essential for real-world modeling but often difficult to handle in pure classical logic. The IGnd algorithm integrates these definitions into the grounding process while maintaining its polynomial-time guarantees.

Key Results and Complexity

The primary theoretical result is a proof that for a fixed $k$, the grounding algorithm runs in $O(\ell \cdot n^k)$ time, where $\ell$ is the formula size and $n$ is the domain size. This is a substantial improvement over the $O(n^v)$ complexity of naive methods.

Furthermore, the authors demonstrate high expressivity: any formula with at most $k$ variables (the $FO^k$ fragment) can be rewritten into a $k$-guarded formula. This implies that the efficiency gains are applicable to a broad range of existing logic models. The algorithm also performs "partial evaluation," resolving known parts of the instance data early to minimize the workload for the subsequent SAT solver.

Conclusion and Future Work

While the algorithm provides a polynomial-time guarantee, the complexity still depends on $k$ in the exponent. Problems requiring high treewidth (high $k$) will remain computationally demanding. Additionally, the current requirement that guards consist only of instance predicates (rather than expansion predicates) is a constraint that future research might seek to relax.

The paper positions MX as a bridge between Answer Set Programming (ASP) and classical logic, combining the intuitive semantics of the latter with the recursive power of the former. Future work will focus on extensive empirical benchmarking of the prototype implementation against established ASP solvers to evaluate real-world performance.

Summary updated

BibTeX
@inproceedings{patterson2007grounding,
  author = {Murray Patterson and Yongmei Liu and Eugenia Ternovska and Arvind Gupta},
  title = {{Grounding for Model Expansion in k-Guarded Formulas with Inductive Definitions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
}
Figure