Journal of Logic and Computation Advance Access originally published online on May 7, 2007
Journal of Logic and Computation 2007 17(3):415-452; doi:10.1093/logcom/exm007
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||
Original Articles |
A Logic for Concepts and Similarity
School of Computer Science and Information Systems, Birkbeck College, Malet Street, London WC1E 7HX, UK. E-mail: mikhail{at}dcs.bbk.ac.uk
Department of Computer Science, University of Liverpool, Liverpool L69 3BX, UK. E-mail: dmitry{at}csc.liv.ac.uk; frank{at}csc.liv.ac.uk
School of Computer Science and Information Systems, Birkbeck College, Malet Street, London WC1E 7HX, UK. E-mail: michael{at}dcs.bbk.ac.uk
Received 23 February 2006.
 |
Abstract |
|---|
Categorization of objects into classes is currently supported by (at least) two `orthogonal' methods. In logic-based approaches, classifications are defined through ontologies or knowledge bases which describe the existing relationships among terms. Description logic (DL) has become one of the most successful formalisms for representing such knowledge bases, in particular because theoretically well-founded and efficient reasoning tools have been readily available.
In numerical approaches, classifications are obtained by first computing similarity (or proximity) measures between objects and then categorizing them into classes by means of Voronoi tessellations, clustering algorithms, nearest neighbour computations, etc.
In many areas such as bioinformatics, computational linguistics or medical informatics, these two methods have been used independently of each other: although both of them are often applied to the same domain (and even by the same researcher), up to now no formal interaction mechanism has been developed.
In this article, we propose a DL-based integration of the two classification methods. Our formalism, called 
, extends the expressive DL 
by means of the constructors of the similarity logic 
which allow definitions of concepts in terms of both comparative and absolute similarity. In the combined knowledge base the user should declare the similarity spaces where the new operators are interpreted.
Of course, can only be useful if classifications with this logic are supported by automated reasoning tools. We lay theoretical foundations for the development of such tools by showing that reasoning problems for can be decomposed into the corresponding problems for its DL-part and similarity part . Then we investigate reasoning in and prove that consistency and many other reasoning problems are ExpTime-complete for this logic. Using this result and a recent complexity result of Pratt-Hartmann for , we prove that reasoning in is NExpTime-complete.
As the `closer' operator of has the same expressive power as the standard implication > of conditional logic, these results may have interesting consequences for conditional logic as well.
Keywords: similarity logic; description logic; ontology; complexity; conditional logic