On the Succinctness of Some Modal Logics

16:30 26th February 2013 ( week 7, Hilary Term 2013 )Lecture Theatre B
One way of comparing knowledge representation formalisms that has attracted attention recently is in terms of representational succinctness, i.e., we can ask whether one of the formalisms allows for a more `economical' encoding of information than the other. Proving that one language is more succinct than another becomes harder when the underlying semantics is stronger. We propose to use Formula Size Games (as put forward by Adler and Immerman, but we present them as games for one player, called Spoiler), games that are played on two sets of models, and that directly link the length of a play in which Spoiler wins the game with the size of a formula, i.e., a formula that is true in the first set of models but false in all models of the second set. Using Formula Size Games, we prove the following succinctness results for mdimensional modal logic, where one has m modalities I: (1) on general Kripke models (and also on binary trees), a definition $\boxi{\forall_\Gamma}\varphi = \bigwedge_{i \in \Gamma}[i]\varphi$ (with $\Gamma \subseteq I$) makes the resulting language exponentially more succinct for $m > 1$; (2) several modal logics use such abbreviations $\boxi{\forall_\Gamma}\varphi$, e.g., in description logics the construct corresponds to adding role disjunctions, and an epistemic interpretation of it is `everybody in $\Gamma$ knows'. Indeed, we show that on epistemic models (i.e, $\mathbf{S}_5$models), the language with $\boxi{\forall_\Gamma}\varphi$ becomes more succinct for $m > 3$; (3) the results for the language with `everybody knows' also hold for a language with `somebody knows', and (4) on epistemic models, Public Announcement Logic is exponentially more succinct than epistemic logic, if $m > 3$. The latter settles an open problem raised by Lutz.
This is joint work with Tim French, Petar Iliev and Barteld Kooi.