Extending the description logic εL with threshold concepts induced by concept measures

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 tau epsilon L(m) of extensions of the lightweight Description Logic epsilon L 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-(sic)t for (sic) is an element of {<, <=, >, >=} then collect all the individuals that belong to C with degree (sic)t. The logic tau epsilon L(m) extends epsilon L with threshold concepts whose semantics is defined relative to a function m. To construct appropriate graded membership functions, we show how concept measures similar to (which are graded generalizations of subsumption or equivalence between concepts) can be used to define graded membership functions m(similar to). Then we introduce a large class of concept measures, called simi-d, for which the logics tau epsilon L(m(similar to)) have good algorithmic properties. Basically, we show that reasoning in. tau epsilon L(m(similar to)) is NP/coNPcomplete 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.