Combining answer set programming with description logics for the semantic web

Thomas Eiter, Thomas Lukasiewicz, Roman Schindlauer, Hans Tompits

2004 · 253 citations · 19 references

Concepts

TL;DR

The paper proposes integrating answer set programming with description logics SHIF(D) and SHOIN(D) to combine rules and ontologies in the Semantic Web. It introduces dl‑programs, defines strong and weak answer set semantics via reductions to positive dl‑programs, and gives fixpoint characterizations for computing minimal Herbrand models. The approach enables building rules on top of ontologies (and, to a limited extent, ontologies on top of rules), shows that strong answer sets generalize ordinary answer sets, and characterizes the complexity of deciding their existence.

Abstract

Towards the integration of rules and ontologies in the Semantic Web, we propose a combination of logic programming under the answer set semantics with the description logics SHIF(D) and SHOIN(D), which underly the Web ontology languages OWL Lite and OWL DL, respectively. This combination allows for building rules on top of ontologies but also, to a limited extent, building ontologies on top of rules. We introduce description logic programs (dl-programs), which consist of a description logic knowledge base L and a finite set of description logic rules (dl-rules) P. Such rules are similar to usual rules in logic programs with negation as failure, but may also contain queries to L, possibly default negated, in their bodies. We define Herbrand models for dl-programs, and show that satisfiable positive dl-programs have a unique least Her-brand model. More generally, consistent stratified dl-programs can be associated with a unique minimal Her-brand model that is characterized through iterative least Herbrand models. We then generalize the (unique) minimal Herbrand model semantics for positive and stratified dl-programs to a strong answer set semantics for all dl-programs, which is based on a reduction to the least model semantics of positive dl-programs. We also define a weak answer set semantics based on a reduction to the answer sets of ordinary logic programs. Strong answer sets are weak answer sets, and both properly generalize answer sets of ordinary normal logic programs. We then give fixpoint characterizations for the (unique) minimal Herbrand model semantics of positive and stratified dl-programs, and show how to compute these models by finite fixpoint iterations. Furthermore, we give a precise picture of the complexity of deciding strong and weak answer set existence for a dl-program.

References

19