Comparative similarity, tree automata, and diophantine equations

Mikhail Sheremet, Dmitry Tishkovsky, Frank Wolter, Michael Zakharyaschev

    Research output: Chapter in Book/Report/Conference proceedingChapter


    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. © Springer-Verlag Berlin Heidelberg 2005.
    Original languageEnglish
    Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.
    PublisherSpringer Nature
    Number of pages14
    Publication statusPublished - 2005
    Event12th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2005 - Montego Bay
    Duration: 1 Jul 2005 → …

    Publication series

    NameLecture Notes in Artificial Intelligence


    Other12th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2005
    CityMontego Bay
    Period1/07/05 → …


    Dive into the research topics of 'Comparative similarity, tree automata, and diophantine equations'. Together they form a unique fingerprint.

    Cite this