Closer representation and reasoning
Mikhail Sheremet, Dmitry Tishkovsky, Frank Wolter, Michael Zakharyaschev · BIROn (Birkbeck, University of London) · 2005
We argue that orthodox tools for defining concepts in the framework of description logic should often be augmented with constructors that could allow definitions in terms of similarity (or closeness). We present a corresponding logical formalism with the binary operator ‘more similar or closer to X than to Y ’ and investigate its computational behaviour in different distance (or similarity) spaces. The concept satisfiability problem turns out to be ExpTime-complete for many classes of distances spaces no matter whether they are required to be symmetric and/or satisfy the triangle inequality. Moreover, the complexity remains the same if we extend the language with the operators ‘somewhere in the neighbourhood of radius a’ where a is a non-negative rational number. However, for various natural subspaces of the real line R (and Euclidean spaces of higher dimensions) even the similarity logic with the sole ‘closer’ operator turns out to be undecidable. This quite unexpected result is proved by reduction of the solvability problem for Diophantine equations (Hilbert’s 10th problem). “There is nothing more basic to thought and language than our sense of similarity; our sorting of things into kinds.” (Quine 1969)