text: Efficiently querying Description Logic (DL) ontologies is becoming a vital task in various data-intensive DL applications. Considered as a basic service for answering object queries over DL ontologies, instance checking can be realized by using the most specific concept (MSC) method, which converts instance checking into subsumption problems. This method, however, loses its simplicity and efficiency when applied to large and complex ontologies, as it tends to generate very large MSCs that could lead to intractable reasoning. In this paper, we propose a revision to this MSC method for DL SHI , allowing it to generate much simpler and smaller concepts that are specific enough to answer a given query. With independence between computed MSCs, scalability for query answering can also be achieved by distributing and parallelizing the computations. An empirical evaluation shows the efficacy of our revised MSC method and the significant efficiency achieved when using it for answering object queries.
  @cite_30: Computing the least common subsunier (les) is an inference task that can be used to support, the "bottom-up" construction of knowledge bases for KR systems based on description logics. Previous work on how to compute the lcs has concentrated on description logics that allow for universal value restrictions, but not for existential restrictions. The main new contribution of this paper is the treatment of description logics with existential restrictions. Our approach for computing the lcs is based on an appropriate representation of concept descriptions by certain trees, and a characterization of subsumption by homomorphisins between these trees. The lcs operation then corresponds to the product operation on trees.
  @cite_26: Computing least common subsumers (Ics) and most specific concepts (msc) are inference tasks that can support the bottom-up construction of knowledge bases in description logics. In description logics with existential restrictions, the most specific concept need not exist if one restricts the attention to concept descriptions or acyclic TBoxes. In this paper, we extend the notions les and msc to cyclic TBoxes. For the description logic EC (which allows for conjunctions, existential restrictions, and the top-concept), we show that the les and msc always exist and can be computed in polynomial time if we interpret cyclic definitions with greatest fixpoint semantics.
  @cite_36: 
  @cite_42: Computing the most specific concept (msc) is an inference task that allows to abstract from individuals defined in description logic (DL) knowledge bases. For DLs that allow for existential restrictions or number restrictions, however, the msc need not exist unless one allows for cyclic concepts interpreted with the greatest fixed-point semantics. Since such concepts cannot be handled by current DL-systems, we propose to approximate the msc. We show that for the DL ALE, which has concept conjunction, a restricted form of negation, existential restrictions, and value restrictions as constructors, approximations of the msc always exist and can effectively be computed.
  @cite_24: Representation and management of knowledge.- A hybrid representation formalism.- Reasoning in the formalism.- Terminological cycles.- Belief revision.- The revision in terminological systems.- Terminological reason maintenance.- Summary and outlook.- The universal term-forming formalism U.- Overview of formalism and systems.
  @cite_31: 
  @cite_10: Computing least common subsumers (lcs) and most specific concepts (msc) are inference tasks that can be used to support the bottom up'''' construction of knowledge bases for KR systems based on description logic. For the description logic ALN, the msc need not always exist if one restricts the attention to acyclic concept descriptions. In this paper, we extend the notions lcs and msc to cyclic descriptions, and show how they can be computed. Our approach is based on the automata-theoretic characterizations of fixed-point semantics for cyclic terminologies developed in previous papers.
summary: The idea of most specific concept for instance checking was first discussed in @cite_24 , and later extensively studied by @cite_36 @cite_31 for the algorithms and the computational complexity. To deal with existential restrictions when computing the most specific concept, @cite_10 @cite_30 @cite_26 discussed the use of cyclic concepts with greatest fixpoint semantics for preservation of information induced by the role assertions, and @cite_42 also proposed an approximation for most specific concept in DLs with existential restrictions.