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.
Introduction
In classical logic programming, such as Prolog or standard Answer Set Programming (ASP), predicates operate on data objects. Higher-order logic programming (HOLP) extends this paradigm by allowing predicates to take other predicates as arguments. This shift offers immense expressive power and facilitates code reusability through meta-programming patterns. However, defining a robust "stable model semantics"—the mathematical foundation of modern ASP solvers—for higher-order programs has remained a significant challenge for decades.
This paper introduces a formal stable model semantics for HOLP by leveraging Approximation Fixpoint Theory (AFT). By moving away from purely syntactic transformations and toward an algebraic framework, the proposed semantics successfully extends the classic results of first-order logic to a higher-order setting while maintaining the core properties that make ASP effective.
The Challenge of Higher-Order Negation
The primary hurdle in defining stable models for higher-order logic is the treatment of negation. In standard logic programming, stable models are defined using the Gelfond-Lifschitz transform (the "reduct"), which relies on identifying explicit occurrences of negation in the program's syntax.
In higher-order logic, negation can be "hidden" or encapsulated within abstractions. For example, a predicate neg might be defined as neg X ← ~X. When this abstraction is passed as an argument to another predicate, the traditional syntactic reduct becomes difficult, if not impossible, to apply. To resolve this, a framework is needed that handles negation based on its functional behavior rather than its syntactic appearance.
Methodology: Approximation Fixpoint Theory
Rather than forcing a syntactic reduct onto higher-order logic, this research utilizes Approximation Fixpoint Theory (AFT). AFT is an algebraic framework that provides a standardized "recipe" for defining various semantics (Stable, Well-Founded, Kripke-Kleene) for non-monotonic systems.
The authors' approach involves three key steps:
- Three-Valued Interpretation: Higher-order predicates are interpreted as functions that accept two-valued arguments but return three-valued results (true, false, or unknown).
- The Approximator ($A_P$): A semantic operator is constructed to work on pairs of interpretations, representing the boundary between "certain" knowledge and "possible" knowledge.
- Lattice Theory Application: Once the operator is defined, the stable model and well-founded semantics emerge naturally from the underlying lattice theory of AFT.
This methodology ensures that the new semantics is a genuine generalization: when applied to standard first-order programs, it produces results identical to the classic Gelfond-Lifschitz or Przymusinski semantics.
Key Insights and Theoretical Results
Generalization and Minimality
The proposed framework preserves the core requirements of logic programming. The authors prove that all stable models within this higher-order framework are minimal models. Furthermore, they demonstrate that the semantics coincides perfectly with classical stable model semantics for propositional and first-order programs.
The "Free" Semantics Benefit
By adopting AFT, the research does not merely define "Stable Models." It simultaneously provides Supported, Kripke-Kleene, and Well-Founded semantics for higher-order logic. This unified approach ensures consistency across different semantic interpretations.
Stratification in HOL
The paper defines a new class of "stratified" higher-order programs. The authors demonstrate that for these programs, the complex three-valued semantics collapses into a unique, intuitive two-valued model. This mirrors a fundamental result in classical logic programming, where stratification guarantees a single, well-defined answer set.
Applications and Expressive Power
To evaluate the utility of the framework, the authors modeled several complex 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.
The ability to model PSPACE-complete problems suggests that HOLP under stable model semantics is significantly more expressive than standard Datalog or ASP. The use of "meta-predicates" (e.g., a maximal predicate) allows for high levels of reusability across disparate domains, such as finding a maximal clique or a maximal set of arguments in an abstract framework.
Conclusion
This work establishes a robust theoretical foundation for higher-order ASP. While the theory is sound, two primary areas for future work remain:
- Implementation: Building an efficient "Higher-Order ASP Solver" requires overcoming significant engineering hurdles, particularly in grounding and solving abstractions that current first-order solvers are not designed to handle.
- Complexity Analysis: While the language can handle PSPACE-complete problems, a full characterization of the expressive power for $k$-order programs is still required.
Ultimately, higher-order logic programming under the stable model semantics represents a powerful and versatile formalism that could serve as the basis for the next generation of knowledge representation and reasoning systems.
Summary updated