@inbook{4bdf82bae183491db2d69417d0e6e834,

title = "Comparative similarity, tree automata, and diophantine equations",

abstract = "The notion of comparative similarity 'X is more similar or closer to Y than to Z' has been investigated in both foundational and applied areas of knowledge representation and reasoning, e.g., in concept formation, similarity-based reasoning and areas of bioinformatics such as protein sequence alignment. In this paper we analyse the computational behaviour of the 'propositional' logic with the binary operator 'closer to a set τ1 than to a set τ2 and nominals interpreted over various classes of distance (or similarity) spaces. In particular, using a reduction to the emptiness problem for certain tree automata, we show that the satisfiability problem for this logic is ExpTime-complete for the classes of all finite symmetric and all finite (possibly non-symmetric) distance spaces. For finite subspaces of the real line (and higher dimensional Euclidean spaces) we prove the undecidability of satisfiability by a reduction of the solvability problem for Diophantine equations. As our 'closer' operator has the same expressive power as the standard operator > of conditional logic, these results may have interesting implications for conditional logic as well. {\textcopyright} Springer-Verlag Berlin Heidelberg 2005.",

author = "Mikhail Sheremet and Dmitry Tishkovsky and Frank Wolter and Michael Zakharyaschev",

year = "2005",

language = "English",

volume = "3835",

series = "Lecture Notes in Artificial Intelligence",

publisher = "Springer Nature",

pages = "651--665",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.",

address = "United States",

note = "12th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2005 ; Conference date: 01-07-2005",

}