Succinctness of epistemic languages
Tim French, Wiebe van der Hoek, Petar Iliev, Barteld P. Kooi · UWA Profiles and Research Repository (UWA) · 2011
Proving that one language is more succinct than an-other becomes harder when the underlying seman-tics is stronger. We propose to use Formula-Size Games (as put forward by Adler and Immerman, 2003), games that are played on two sets of mod-els, and that directly link the length of play with the size of the formula. Using FSGs, we prove three succinctness results form-dimensional modal logic: (1) In system Km, a notion of ‘everybody knows ’ makes the resulting language exponentially more succinct form> 1 (2) In S5m, the same lan-guage becomes more succinct for m> 3 and (3) Public Announcement Logic is exponentially more succinct than S5m, if m> 3. The latter settles an open problem raised by Lutz, 2006. 1