Conjunctive Reasoning on Fuzzy Taxonomies with Order-Sorted Feature Logic

Taxonomies are frequently used to represent knowledge; a taxonomy is a set of concepts partially ordered by a subsumption (is-a) relation. Recently, the CEDAR project has proposed a CEDAR Semantic Web reasoner based on OSF logic, which has shown very promising results with respect to both efficiency and scalability. Indeed, the basic operations behind the reasoning mechanism of CEDAR amount to answering Boolean queries on a taxonomy. For instance, CEDAR answers a conjunctive query on a taxonomy by computing the greatest lower bound of a subset of its elements. This paper proposes a generalization of this operation to the setting where the taxonomy is regarded as a fuzzy partially ordered set and an answer to a conjunctive query is associated with a satisfaction (approximation) degree. A conjunctive query on the fuzzy taxonomy can be answered by applying the same encoding technique of the CEDAR reasoner, while the approximation degree of an answer can be computed by adapting shortest path algorithms for directed acyclic graphs that can be further optimized thanks to the information provided by the encoding.