Succinctness of Epistemic Languages

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

doi:10.5591/978-1-57735-516-8/IJCAI11-153

Succinctness of Epistemic Languages

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

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 881-885.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-153

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 those games, 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 S5, 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.

Tim French, Wiebe van der Hoek, Petar Iliev, and Barteld P. Kooi. 2011. Succinctness of Epistemic Languages. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 881–885. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-153

@inproceedings{ijcai2011p153,
  title     = {Succinctness of Epistemic Languages},
  author    = {French, Tim and van der Hoek, Wiebe and Iliev, Petar and Kooi, Barteld P.},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {881--885},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-153},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-153},
}

TY  - CPAPER
TI  - Succinctness of Epistemic Languages
AU  - French, Tim
AU  - van der Hoek, Wiebe
AU  - Iliev, Petar
AU  - Kooi, Barteld P.
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 881
EP  - 885
DO  - 10.5591/978-1-57735-516-8/IJCAI11-153
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-153
ER  -