Propositional interval neighborhood logics: Expressiveness, decidability, and undecidable extensions

Davide Bresolin, Valentin Goranko, Angelo Montanari, Guido Sciavicco

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    In this paper, we investigate the expressiveness of the variety of propositional interval neighborhood logics (PNL), we establish their decidability on linearly ordered domains and some important subclasses, and we prove the undecidability of a number of extensions of PNL with additional modalities over interval relations. All together, we show that PNL form a quite expressive and nearly maximal decidable fragment of Halpern–Shoham’s interval logic HS.
    Original languageEnglish
    JournalAnnals of Pure and Applied Logic
    Volume161
    Issue number3
    Pages (from-to)289-304
    ISSN0168-0072
    DOIs
    Publication statusPublished - 2009

    Keywords

    • Two-variable fragment
    • Neighborhood interval logics
    • Undecidability
    • Expressiveness
    • Decidability

    Fingerprint Dive into the research topics of 'Propositional interval neighborhood logics: Expressiveness, decidability, and undecidable extensions'. Together they form a unique fingerprint.

    Cite this