Succinctness of Epistemic Languages
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.
Cite
Text
French et al. "Succinctness of Epistemic Languages." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-153Markdown
[French et al. "Succinctness of Epistemic Languages." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/french2011ijcai-succinctness/) doi:10.5591/978-1-57735-516-8/IJCAI11-153BibTeX
@inproceedings{french2011ijcai-succinctness,
title = {{Succinctness of Epistemic Languages}},
author = {French, Tim and van der Hoek, Wiebe and Iliev, Petar and Kooi, Barteld P.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2011},
pages = {881-886},
doi = {10.5591/978-1-57735-516-8/IJCAI11-153},
url = {https://mlanthology.org/ijcai/2011/french2011ijcai-succinctness/}
}