- Titel
- Complexity and Succinctness of Public Announcement Logic
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-793353
- Schriftenreihe
- LTCS-Report
- Bandnummer
- 05-09
- Erstveröffentlichung
- 2005
- DOI
- https://doi.org/10.25368/2022.152
- Abstract (EN)
- There is a recent trend of extending epistemic logic (EL) with dynamic operators that allow to express the evolution of knowledge and belief induced by knowledge-changing actions. The most basic such extension is public announcement logic (PAL), which is obtained from EL by adding an operator for truthful publix announcements. In this paper, we consider the computational complexity of PAL and show that it coincides with that of EL. This holds in the single- and multi-agent case, and also in the presence of common knowledge operators. We also prove that there are properties that can be expressed exponentially more succint in PAL than in EL. This shows that, despite the known fact that PAL and EL have the same expressive power, ther eis a benefit in adding the public announcement operator to EL: it exponentially increases the succinctness of formulas without having negative effects on computational complexity.
- Freie Schlagwörter (DE)
- Logik der öffentlichen Verkündung, epistemische Logik
- Freie Schlagwörter (EN)
- public announcement logic, epistemic logic
- Klassifikation (DDC)
- 004
- Klassifikation (RVK)
- ST 136
- Publizierende Institution
- Technische Universität Dresden, Dresden
- Version / Begutachtungsstatus
- angenommene Version / Postprint / Autorenversion
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa2-793353
- Veröffentlichungsdatum Qucosa
- 31.05.2022
- Dokumenttyp
- Bericht
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis
CC BY 4.0