by Lutz Schröder and 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. As a consequence, recent results on coalgebraic modal logic, in particular generic decision procedures and upper complexity bounds, become applicable to arbitrary rank 1 modal logics, without regard to their semantic status; we thus obtain purely syntactic versions of these results. As an extended example, we apply our framework to recently defined deontic logics.
Reference:
Lutz Schröder and Dirk Pattinson: Rank-1 Modal Logics are Coalgebraic, In Wolfgang Thomas, Pascal Weil, eds.: International Symposium on Theoretical Aspects of Computer Science (STACS 07), Lecture Notes in Computer Science, vol. 4393, pp. 573–585, Springer, 2007. Extended version available [preprint]
Bibtex Entry:
@InProceedings{SchroderPattinson07mcs,
author = {Lutz Schr{\"o}der and Dirk Pattinson},
title = {Rank-1 Modal Logics are Coalgebraic},
year = {2007},
editor = {Wolfgang Thomas and Pascal Weil},
booktitle = {International Symposium on Theoretical Aspects of Computer Science (STACS 07)},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {4393},
pages = {573-585},
keywords = {semantics deduction decidability complexity modal logic coalgebra},
url = {http://dx.doi.org/10.1007/978-3-540-70918-3_49},
comment = { <a href = "http://www8.informatik.uni-erlangen.de/~schroeder/papers/rank1coalg.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. As a consequence, recent results on coalgebraic modal logic, in particular generic decision procedures and upper complexity bounds, become applicable to arbitrary rank 1 modal logics, without regard to
their semantic status; we thus obtain purely syntactic versions of these results. As an extended example, we apply our framework to recently defined deontic logics.
},
note = {<a href="http://www8.informatik.uni-erlangen.de/~schroeder/papers/rank1coalg-ext.pdf">Extended version</a> available},
}