Search

In applications of AI systems where exact definitions of the important notions of the application domain are hard to come by, the use of traditional logic-based knowledge representation languages such as Description Logics may lead to very large and unintuitive definitions, and high complexity of reasoning. To overcome this problem, we define new concept constructors that allow us to define concepts in an approximate way. To be more precise, we present a family τ EL (m) of extensions of the lightweight Description Logic EL that use threshold constructors for this purpose. To define the semantics of these constructors we employ graded membership functions m , which for each individual in an interpretation and concept yield a number in the interval [ 0 , 1 ] expressing the degree to which the individual belongs to the concept in the interpretation. Threshold concepts C ⋈ t for ⋈ ∈ { < , ≤ , > , ≥ } then collect all the individuals that belong to C with degree ⋈ t. The logic τ EL (m) extends EL with threshold concepts whose semantics is defined relative to a function m. To construct appropriate graded membership functions, we show how concept measures ∼ (which are graded generalizations of subsumption or equivalence between concepts) can be used to define graded membership functions m ∼. Then we introduce a large class of concept measures, called simi-d , for which the logics τ EL (m ∼) have good algorithmic properties. Basically, we show that reasoning in τ EL (m ∼) is NP/coNP-complete without TBox, PSpace-complete w.r.t. acyclic TBoxes, and ExpTime-complete w.r.t. general TBoxes. The exception is the instance problem, which is already PSpace-complete without TBox w.r.t. combined complexity. While the upper bounds hold for all elements of simi-d , we could prove some of the hardness results only for a subclass of simi-d. This article considerably improves on and generalizes results we have shown in three previous conference papers and it provides detailed proofs of all our results. [ABSTRACT FROM AUTHOR]

There are multiple ways of defining nonmonotonic inference relations based on a conditional knowledge base. While the axiomatic system P is an important standard for such plausible nonmonotonic reasoning, inference relations obtained from system Z or from c-representations have been designed which go beyond system P by selecting preferred models for inference. For any class of models M , we propose the notion of weakly skeptical inference, first introduced in an ECAI conference paper this article revises and extends, that lies between skeptical and credulous inference with respect to M. Weakly skeptical c-inference properly extends skeptical c-inference, but avoids disadvantages of a too liberal credulous c-inference. We extend the concepts of skeptical, weakly skeptical, and credulous c-inference modes by taking models obtained from different minimality criteria into account. We illustrate the usefulness of the obtained inference relations and show that they fulfill various desirable properties put forward for nonmonotonic reasoning. Furthermore, we elaborate in detail the interrelationships among the inference relations when taking the different inference modes and various classes of minimal models into account. [ABSTRACT FROM AUTHOR]