Succinctness of Epistemic Languages
Wiebe van der Hoek, Petar Iliev, Tim French and Barteld Kooi
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 for m-dimensional modal logic: (1) In system Km, a notion of ‘everybody knows’ makes the resulting language exponentially more succinct for m > 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.