Rank-1 modal logics are coalgebraic (bibtex)

by Lutz Schröder, Dirk Pattinson

Abstract:

Coalgebras provide a unifying semantic framework for a wide variety of modal logics. It has previously been shown that the class of coalgebras for an endofunctor can always be axiomatised in rank 1. Here we establish the converse, i.e. every rank 1 modal logic has a sound and strongly complete coalgebraic semantics. This is achieved by constructing for a given modal logic a canonical coalgebraic semantics, consisting of a signature functor and interpretations of modal operators, which turns out to be final among all such structures. The canonical semantics may be seen as a coalgebraic reconstruction of neighbourhood semantics, broadly construed. A finitary restriction of the canonical semantics yields a canonical weakly complete semantics which moreover enjoys the Hennessy-Milner property. As a consequence, the machinery of coalgebraic modal logic, in particular generic decision procedures and upper complexity bounds, becomes applicable to arbitrary rank 1 modal logics, without regard to their semantic status; we thus obtain purely syntactic versions of such results. As an extended example, we apply our framework to recently defined deontic logics. In particular, our methods lead to the new result that these logics are strongly complete.

Reference:

Rank-1 modal logics are coalgebraic (Lutz Schröder, Dirk Pattinson), In Journal of Logic and Computation, vol. 20(5), pp. 1113–1147, 2010. [preprint]

Bibtex Entry:

@Article{SchroderPattinson08b, author = {Lutz Schr{\"o}der and Dirk Pattinson}, title = {Rank-1 modal logics are coalgebraic }, year = {2010}, journal = {Journal of Logic and Computation}, volume = {20}, pages = {1113-1147}, number = {5}, keywords = {Modal logic coalgebra neighbourhood frames deontic logic decision procedures}, url = {http://logcom.oxfordjournals.org/content/20/5/1113.abstract}, comment = { <a href = "http://www8.informatik.uni-erlangen.de/~schroeder/papers/rank1coalg-ext.pdf"> [preprint] </a>}, abstract = {Coalgebras provide a unifying semantic framework for a wide variety of modal logics. It has previously been shown that the class of coalgebras for an endofunctor can always be axiomatised in rank 1. Here we establish the converse, i.e. every rank 1 modal logic has a sound and strongly complete coalgebraic semantics. This is achieved by constructing for a given modal logic a canonical coalgebraic semantics, consisting of a signature functor and interpretations of modal operators, which turns out to be final among all such structures. The canonical semantics may be seen as a coalgebraic reconstruction of neighbourhood semantics, broadly construed. A finitary restriction of the canonical semantics yields a canonical weakly complete semantics which moreover enjoys the Hennessy-Milner property. As a consequence, the machinery of coalgebraic modal logic, in particular generic decision procedures and upper complexity bounds, becomes applicable to arbitrary rank 1 modal logics, without regard to their semantic status; we thus obtain purely syntactic versions of such results. As an extended example, we apply our framework to recently defined deontic logics. In particular, our methods lead to the new result that these logics are strongly complete. }}

Powered by bibtexbrowser