Succinctness of Epistemic Languages

Tim French, Wiebe van der Hoek, Petar Iliev, Barteld P. Kooi

Abstract

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, 2003), games that are played on two sets of models, 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 language 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.
BibTeX
@inproceedings{french2011succinctness,
  author = {Tim French and Wiebe van der Hoek and Petar Iliev and Barteld P. Kooi},
  title = {{Succinctness of Epistemic Languages}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  doi = {10.5591/978-1-57735-516-8/ijcai11-153},
}

Loading related content...

Figure