A Uniform Integration of Higher-Order Reasoning and External Evaluations in Answer-Set Programming

Thomas Eiter, Giovambattista Ianni, Roman Schindlauer, Hans TompitsIJCAI 2005 · OpenReview

Abstract

This paper introduces HEX programs, a significant extension to Answer-Set Programming (ASP) that incorporates higher-order atoms and external evaluations. By allowing logic programs to treat predicates as variables and query external software, HEX programs provide a unified, fully declarative framework. This architecture is particularly suited for complex Semantic Web applications, ontology reasoning, and knowledge integration. The authors extend the well-known answer-set semantics to this class of programs, discuss the theoretical complexity, and present a preliminary prototype implementation.

Introduction

Answer-Set Programming (ASP) has emerged as a highly successful declarative paradigm for solving complex AI problems, including planning, diagnosis, and information integration. However, the rise of the Semantic Web has highlighted two major limitations in standard ASP: a lack of meta-reasoning capabilities and poor interoperability with external sources.

Standard ASP operates within a closed world and cannot easily reason about its own predicates or dynamically exchange predicate symbols with constant symbols. Furthermore, it struggles to natively query external software, such as Description Logic (DL) reasoners or web APIs. While other logic-based formalisms like TRIPLE or F-Logic offer some higher-order features, they often lack precise semantics or restrict expressiveness to maintain efficiency. HEX programs are designed to bridge this gap, providing a fully declarative ASP extension that handles both higher-order reasoning and external software interfacing without sacrificing non-deterministic problem-solving capabilities.

The HEX Program Framework

HEX programs (Higher-order + EXternal programs) introduce two novel syntactic features to the ASP language:

  1. Higher-Order Atoms: These allow variables to be used in the predicate position. For instance, a rule like C(X) <- subClassOf(D, C), D(X) allows the program to dynamically instantiate the predicate D, enabling meta-level reasoning over the schema itself.
  2. External Atoms: These allow the program to delegate the truth value of an atom to an external source. An example is #reach[edge, a](X), which passes a graph edge and node a to an external function (written in C++ or Python) to compute reachable nodes, returning the results directly to the logic program.

Semantic Foundations

To provide a rigorous mathematical foundation for HEX programs, the authors move beyond the traditional Gelfond-Lifschitz reduct. The standard reduct struggles with the minimality of answer sets when external or aggregate atoms are involved. Instead, the authors utilize the FLP-reduct (developed by Faber, Leone, and Pfeifer). This modern reduct naturally accommodates external computations and recursion, ensuring that the resulting answer sets remain minimal and logically sound while conservatively extending both standard ASP and HiLog semantics.

Theoretical Unification and Expressiveness

A primary insight of this research is that external atoms serve as a universal abstraction rather than a mere interface for API calls. The authors demonstrate that many existing, disparate ASP extensions can be perfectly simulated within the HEX framework. Specifically, the paper provides formal proofs that HEX programs can capture the semantics of:

  • Ordinary programs with aggregates (e.g., sum, count).
  • Description Logic (DL) programs.
  • Monotone cardinality programs.

This synergy is particularly powerful for the Semantic Web. A HEX program can use an external atom to pull RDF triples from a URI and then use higher-order atoms to dynamically reason about the classes and properties defined in those triples, facilitating seamless ontology alignment.

Complexity and Implementation

Surprisingly, the addition of higher-order atoms does not increase the theoretical complexity of the language compared to ordinary ASP. The complexity is primarily driven by the external functions. The paper establishes that deciding if a HEX program has an answer set is NEXP^NP-complete (or NEXP-complete if the program lacks disjunctions), assuming the external functions can be evaluated in exponential time relative to the domain size.

The authors developed an experimental prototype that evaluates HEX programs by translating them into ordinary ASP. This implementation utilizes a technique called "e-stratification" to handle negation alongside external atoms, ensuring stable evaluation for a specific class of programs.

Conclusion and Future Work

HEX programs represent a robust step toward a unified logic programming framework for the modern web. While the current prototype is effective for e-stratified programs, the authors acknowledge that non-monotonic external atoms can create challenges for answer-set existence. Future work focuses on developing highly optimized evaluation algorithms for general, unstratified HEX programs, with the ultimate goal of deploying these tools in personalized Web information systems and large-scale knowledge integration tasks.

Summary updated

Abstract

We introduce HEX programs, which are nonmonotonic logic programs admitting higher-order atoms as well as external atoms, and we extend the well-known answer-set semantics to this class of programs. Higher-order features are widely acknowledged as useful for performing meta-reasoning, among other tasks. Furthermore, the possibility to exchange knowledge with external sources in a fully declarative framework such as Answer-Set Programming (ASP) is nowadays important, in particular in view of applications in the Semantic Web area. Through external atoms, HEX programs can model some important extensions to ASP, and are a useful KR tool for expressing various applications. Finally, complexity and implementation issues for a preliminary prototype are discussed.
BibTeX
@inproceedings{eiter2005uniform,
  author = {Thomas Eiter and Giovambattista Ianni and Roman Schindlauer and Hans Tompits},
  title = {{A Uniform Integration of Higher-Order Reasoning and External Evaluations in Answer-Set Programming}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
  url = {https://openreview.net/forum?id=B1-Kerz_Wr},
}
Figure