This chapter presents a novel approach to fuzzy description logic programs (or simply fuzzy dl-programs) under the answer set semantics, which is a tight integration of fuzzy disjunctive logic programs under the answer set semantics with fuzzy description logics. From a different perspective, it is a generalization of tightly coupled disjunctive dl-programs by fuzzy vagueness in both the description logic and the logic program component. The authors show that the new formalism faithfully extends both fuzzy disjunctive logic programs and fuzzy description logics, and that under suitable assumptions, reasoning in the new formalism is decidable. The authors present a polynomial reduction of certain fuzzy dl-programs to tightly coupled disjunctive dl-programs, and we analyze the complexity of consistency checking and query processing for certain fuzzy dl-programs. Furthermore, the authors provide a special case of fuzzy dl-programs for which deciding consistency and query processing can both be done in polynomial time in the data complexity.
TopIntroduction
The Semantic Web (Berners-Lee, 1999; Fensel et al., 2002) aims at an extension of the current World Wide Web by standards and technologies that help machines to understand the information on the Web so that they can support richer discovery, data integration, navigation, and automation of tasks. The main ideas behind it are to add a machine-readable meaning to Web pages, to use ontologies for a precise definition of shared terms in Web resources, to use KR technology for automated reasoning from Web resources, and to apply cooperative agent technology for processing the information of the Web.
The Semantic Web consists of several hierarchical layers, where the Ontology layer, in form of the OWL Web Ontology Language (W3C, 2004; Horrocks et al., 2003), is currently the highest layer of sufficient maturity. OWL consists of three increasingly expressive sublanguages, namely, OWL Lite, OWL DL, and OWL Full. OWL Lite and OWL DL are essentially very expressive description logics with an RDF syntax (Horrocks et al., 2003). As shown in (Horrocks & Patel-Schneider, 2004), ontology entailment in OWL Lite (resp., OWL DL) reduces to knowledge base (un)satisfiability in the description logic SHIF(D) (resp., SHOIN(D)). As a next step in the development of the Semantic Web, one aims especially at sophisticated representation and reasoning capabilities for the Rules, Logic, and Proof layers of the Semantic Web.
In particular, there is a large body of work on integrating rules and ontologies, which is a key requirement of the layered architecture of the Semantic Web. Significant research efforts focus on hybrid integrations of rules and ontologies, called description logic programs (or dl-programs), which are of the form KB=(L,P), where L is a description logic knowledge base, and P is a finite set of rules involving either queries to L in a loose integration (see especially (Eiter et al., 2008; Eiter et al., 2004; Eiter et al., 2006)) or concepts and roles from L as unary resp. binary predicates in a tight integration (see especially (Lukasiewicz, 2007a; Rosati, 2006)).
Other works explore formalisms for handling uncertainty and vagueness / imprecision in the Semantic Web. In particular, formalisms for dealing with uncertainty and vagueness in ontologies have been applied in ontology mapping and information retrieval. Vagueness and imprecision also abound in multimedia information processing and retrieval. Moreover, handling vagueness is an important aspect of natural language interfaces to the Web. There are several recent extensions of description logics, ontology languages, and dl-programs for the Semantic Web by probabilistic uncertainty and by fuzzy vagueness. In particular, dl-programs under probabilistic uncertainty and under fuzzy vagueness have been proposed in (Lukasiewicz, 2005; Lukasiewicz, 2006b) and (Straccia, 2006c; Straccia, 2006b; Lukasiewicz, 2006a), respectively.
In this paper, we continue this line of research. We present tightly coupled fuzzy description logic programs (or simply fuzzy dl-programs) under the answer set semantics, which are a tight integration of fuzzy disjunctive programs under the answer set semantics with fuzzy generalizations of SHIF(D) and SHOIN(D). Even though there has been previous work on fuzzy positive dl-programs (Straccia, 2006c; Straccia, 2006b) and on loosely coupled fuzzy normal dl-programs (Lukasiewicz, 2006a), to our knowledge, this is the first approach to tightly coupled fuzzy disjunctive dl-programs (with default negation in rule bodies). The main contributions of this paper can be briefly summarized as follows: