On the Relative Succinctness of Modal Logics with Union, Intersection and Quantification

摘要

In the study of knowledge representation formalisms, there is a current interest in the question of how different formal languages compare in their ability to compactly express semantic properties. Recently, French et al. [9] have shown that modal logics with a modality for public announcement, for everybody knows, and for somebody knows are all exponentially more succinct than basic modal logic. In this paper we compare the above mentioned logics not with basic modal logic but with each other and also with modal logics that have a modality for distributed knowledge. Interestingly, modal logic with such a modality is more expressive than the other modal logics mentioned, but still we can show that some of those weaker logics are exponentially more succinct than the former. Additionally, we prove that the opposite is also possible: indeed, we show that modal logic with a modality for distributed knowledge is more succinct than modal logic with a modality for everybody knows.