The Stable Model Semantics for Higher-Order Logic Programming

Bart Bogaerts, Angelos Charalambidis, Giannos Chatziagapis, Babis Kostopoulos, Samuele Pollaci, Panos Rondogiannis

TL;DR

This paper introduces a formal Stable Model Semantics for Higher-Order Logic Programming (HOL). By leveraging Approximation Fixpoint Theory (AFT), the authors successfully extend the classic semantics of first-order logic programs to a higher-order setting, allowing predicates to take other predicates as arguments while maintaining the desirable properties of traditional Answer Set Programming (ASP).

What Problem Does This Paper Address?

In classical logic programming (like Prolog or standard ASP), predicates operate on data objects. Higher-order logic programming allows predicates to operate on other predicates, offering immense expressive power and code reusability. However, defining a "stable model semantics"—the mathematical backbone of modern ASP solvers—for higher-order programs has been a long-standing challenge.

The primary hurdle is negation. In standard logic, we define stable models using a "reduct" (the Gelfond-Lifschitz transform), which relies on identifying occurrences of negation in the program's syntax. In higher-order logic, negation can be "hidden" inside abstractions (e.g., a predicate neg defined as neg X ← ~X). This makes traditional syntactic transformations difficult or impossible to apply. The authors aim to provide a robust semantic framework that handles these abstractions naturally.

Methods

Instead of trying to force a syntactic "reduct" onto higher-order logic, the authors use Approximation Fixpoint Theory (AFT).

AFT is a powerful algebraic framework that provides a "recipe" for defining various semantics (Stable, Well-Founded, Kripke-Kleene) for any non-monotonic system. To use this recipe, the authors:

  1. Defined a Three-Valued Semantics: They interpreted higher-order predicates as functions that take two-valued arguments but return three-valued results (true, false, or unknown).
  2. Constructed an Approximator: They developed a semantic operator ($A_P$) that works on pairs of interpretations (representing "certain" vs. "possible" knowledge).
  3. Applied AFT Machinery: Once the operator was defined, the stable model and well-founded semantics "rolled out" automatically from the underlying lattice theory.

This approach ensures that the new semantics is a genuine generalization: if you feed it a standard first-order program, it produces the exact same results as the classic Gelfond-Lifschitz or Przymusinski semantics.

Datasets

As a theoretical paper in logic and computer science, no empirical datasets were used. Instead, the authors evaluated their semantics using complex logic puzzles and computational problems:

  • Max-Clique: Finding the largest fully connected subgraph.
  • Abstract Argumentation: Modeling Dung’s frameworks for dialectical reasoning.
  • Generalized Geography: A PSPACE-complete game played on a graph.

Key Insights and Ideas

  • Negation as Abstraction: The paper highlights that in HOL, negation isn't just a symbol; it's a behavior that can be passed around as a parameter. Their semantics handles this by focusing on the functionality of the predicate rather than its syntactic appearance.
  • The "Free" Semantics Benefit: Because they used AFT, the authors didn't just define "Stable Models." They simultaneously provided Supported, Kripke-Kleene, and Well-Founded semantics for higher-order logic without extra effort.
  • Stratification in HOL: They defined a new class of "stratified" higher-order programs. They proved that for these programs, the complex three-valued semantics collapses into a unique, intuitive two-valued model, mirroring a key result from classical logic programming.
  • Reusability via Templates: The examples demonstrate how HOL allows for "meta-predicates" (like a maximal predicate) that can be defined once and reused across different domains (e.g., finding a maximal clique vs. a maximal set of arguments).

Key Results

  • Generalization: Proved that the proposed semantics coincides with classical stable model semantics for propositional and first-order programs.
  • Minimality: Demonstrated that all stable models in this framework are minimal models, preserving a core requirement of logic programming.
  • Expressive Power: Showed that the language can compactly model PSPACE-complete problems, suggesting it is significantly more expressive than standard Datalog or ASP.
  • Well-Founded Consistency: Proved that if the well-founded model of a program is two-valued, it is the unique stable model.

Limitations and Future Work

The authors acknowledge two main areas for future exploration:

  1. Implementation: While the theory is sound, building an efficient "Higher-Order ASP Solver" is a significant engineering challenge. Current ASP solvers are highly optimized for first-order logic; adapting them for higher-order abstractions will require new grounding and solving techniques.
  2. Complexity Analysis: While they showed the language can handle PSPACE-complete problems, a full characterization of the expressive power (e.g., exactly which complexity classes it captures for $k$-order programs) remains to be completed. They hypothesize that adding stable negation to $k$-order Datalog will significantly boost its reach.

Summary updated

Abstract

We propose a stable model semantics for higher-order logic programs. Our semantics is developed using Approximation Fixpoint Theory (AFT), a powerful formalism that has successfully been used to give meaning to diverse non-monotonic formalisms. The proposed semantics generalizes the classical two-valued stable model semantics of (Gelfond and Lifschitz 1988) as-well-as the three-valued one of (Przymusinski 1990), retaining their desirable properties. Due to the use of AFT, we also get for free alternative semantics for higher-order logic programs, namely supported model, Kripke-Kleene, and well-founded. Additionally, we define a broad class of stratified higher-order logic programs and demonstrate that they have a unique two-valued higher-order stable model which coincides with the well-founded semantics of such programs. We provide a number of examples in different application domains, which demonstrate that higher-order logic programming under the stable model semantics is a powerful and versatile formalism, which can potentially form the basis of novel ASP systems.
BibTeX
@article{bogaerts2024stable,
  author = {Bart Bogaerts and Angelos Charalambidis and Giannos Chatziagapis and Babis Kostopoulos and Samuele Pollaci and Panos Rondogiannis},
  title = {{The Stable Model Semantics for Higher-Order Logic Programming}},
  journal = {Theory Pract. Log. Program},
  year = {2024},
  doi = {10.1017/s1471068424000231},
}

Loading related content...

Figure