From topology to metric: Modal logic and quantification in metric spaces

Mikhail Sheremet, Michael Zakharyaschev, Dmitry Tishkovsky, Frank Wolter

    Research output: Chapter in Book/Report/Conference proceedingChapter

    Abstract

    We propose a framework for comparing the expressive power and computational behaviour of modal logics designed for reasoning about qualitative aspects of metric spaces. Within this framework we can compare such well-known logics as S4 (for the topology induced by the metric), wK4 (for the derivation operator of the topology), variants of conditional logic, as well as logics of comparative similarity. One of the main problems for the new family of logics is to delimit the borders between 'decidable' and 'undecidable.' As a first step in this direction, we consider the modal logic with the operator 'closer to a set τ 0 than to a set τ 1' interpreted in metric spaces. This logic contains S4 with the universal modality and corresponds to a very natural language within our framework. We prove that over arbitrary metric spaces this logic is ExpTime-complete. Recall that over ℝ, ℚ, and ℤ, as well as their finite subspaces, this logic is undecidable. © 2006, the authors.
    Original languageEnglish
    Title of host publicationAdvances in Modal Logic 2006|Adv. Modal Logic
    PublisherCollege Publications
    Pages429-448
    Number of pages19
    Volume6
    ISBN (Print)1904987206, 9781904987208
    Publication statusPublished - 2006
    Event6th Conference on Advances in Modal Logic, AiML-2006 - Noosa, QLD
    Duration: 1 Jul 2006 → …

    Conference

    Conference6th Conference on Advances in Modal Logic, AiML-2006
    CityNoosa, QLD
    Period1/07/06 → …

    Keywords

    • Comparative similarity
    • Conditional logic
    • Metric
    • Topology

    Fingerprint

    Dive into the research topics of 'From topology to metric: Modal logic and quantification in metric spaces'. Together they form a unique fingerprint.

    Cite this