On the succinctness of some modal logics

摘要

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 logic 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 (2003) [1], 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 m-dimensional modal logic, where one has a set of indices for m modalities: (1) on general Kripke models (and also on binary trees), a definition (with ) makes the resulting logic exponentially more succinct for ; (2) several modal logics use such abbreviations , e.g., in description logics the construct corresponds to adding role disjunctions, and an epistemic interpretation of it is ‘everybody in Γ knows’. Indeed, we show that on epistemic models (i.e., -models), the logic with becomes more succinct for ; (3) the results for the logic with ‘everybody knows’ also hold for a logic with ‘somebody knows’, and (4) on epistemic models, Public Announcement Logic is exponentially more succinct than epistemic logic, if . The latter settles an open problem raised by Lutz (2006) [18].