The logic of exact covers: Completeness and uniform interpolation

Dirk Pattinson*

*Corresponding author for this work

    Research output: Contribution to journalConference articlepeer-review

    13 Citations (Scopus)

    Abstract

    We show that all (not necessarily normal or monotone) modal logics that can be axiomatised in rank-1 have the interpolation property, and that in fact interpolation is uniform if the logics just have finitely many modal operators. As immediate applications, we obtain previously unknown interpolation theorems for a range of modal logics, containing probabilistic and graded modal logic, alternating temporal logic and some variants of conditional logic. Technically, this is achieved by translating to and from a new (coalgebraic) logic introduced in this paper, the logic of exact covers. It is interpreted over coalgebras for an endofunctor on the category of sets that also directly determines the syntax. Apart from closure under bisimulation quantifiers (and hence interpolation), we also provide a complete tableaux calculus and establish both the Hennessy-Milner and the small model property for this logic.

    Original languageEnglish
    Article number6571574
    Pages (from-to)418-427
    Number of pages10
    JournalProceedings - Symposium on Logic in Computer Science
    DOIs
    Publication statusPublished - 2013
    Event2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2013 - New Orleans, LA, United States
    Duration: 25 Jun 201328 Jun 2013

    Fingerprint

    Dive into the research topics of 'The logic of exact covers: Completeness and uniform interpolation'. Together they form a unique fingerprint.

    Cite this