Abstract
This thesis makes a contribution to the research efforts of integrating rule-based inference methods with current knowledge representation formalisms in the Semantic Web. Ontology languages such as OWL and RDF Schema seem to be widely accepted and successfully used for semantically enriching knowledge on the Web and thus prepare it for machinereadability. However, these languages are of restricted expressivity if it comes to inferring new from existing knowledge. On the other side, rule formalisms have a long tradition in logic programming, being a common and intuitive tool for problem specifications. It is evident that the Semantic Web needs a powerful rule language complementing its ontology formalisms in order to facilitate sophisticated reasoning tasks. Ontology languages commonly derive from Description Logics. As a fragment of first-order logic, their semantics diverge significantly from logic programming languages like Datalog and its various descendants - especially if we consider the powerful category of non-monotonic logic programming. In order to overcome this gap, different approaches have been presented how to combine Description Logics with rules, varying in the degree of integration. Answer-set programming (ASP) is one of the most prominent and successful semantics for non-monotonic logic programs. The specific treatment of default negation under ASP allows for the generation of multiple models for a single program, which in this respect can be seen as the encoding of a problem specication. Highly efficient reasoners for ASP are available, each extending the core language by various sophisticated features such as aggregates or weak constraints. In the first part of this thesis, 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 show that consistent stratied dl-programs can be associated with a unique minimal Herbrand model that is characterized through iterative least Herbrand models. We then define strong and weak answer-set semantics which both properly generalize answer sets of ordinary normal logic programs, based on a reduction to the least model semantics of positive dl-programs and to the answer-set semantics of ordinary logic programs respectively. We also present a definition of the well-founded semantics for dl-programs, based on a generalization of the notion of unfounded sets. We then give fixpoint characterizations for the (unique) minimal Herbrand model semantics of positive and stratified dl-programs as well as for the wellfounded semantics, and show how to compute these models by finite fixpoint iterations. Furthermore, we give a precise picture of the complexity of deciding answer set existence for a dl-program, and of brave, cautious, and well-founded reasoning. We lay out possible applications of dl-programs and present the implementation of a prototype reasoner. In the second part of the thesis, we generalize our approach to hex-programs, which are nonmonotonic logic programs under the answer-set semantics admitting higher-order atoms as well as external atoms. 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 ASP is particularly important 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. We define syntax and semantics of hex-programs and show how they can be deployed in the context of the Semantic Web. We give a picture of the computation method of hex-programs based on the theory of splitting sets, followed by a discussion on complexity. Then, the implementation of a prototype reasoner for hex-programs is outlined, along with a description how to extend this framework by custom modules. Eventually, we show the usability and versatility of hex-programs and our prototype implementation on the basis of concrete, real-world scenarios.

URL:
http://rewerse.net/publications/rewerse-publications.html#REWERSE-RP-2006-163

BibTeX:

@phdthesis{REWERSE-RP-2006-163,
	author = {Roman Schindlauer},
	title = {Answer-Set Programming for the Semantic Web},
	school = {Institute of Computer Science, LMU, Munich},
	year = {2006},
	note = {PhD Thesis, Institute of Information Systems, Vienna University of Technology, December 2006},
	type = {{Dissertation/Ph.D. thesis}},
	url = {http://rewerse.net/publications/rewerse-publications.html#REWERSE-RP-2006-163}
}