Complexity and Succinctness of Public Announcement Logic

C. LutzC. Lutz

Download

C. Lutz
Complexity and Succinctness of Public Announcement Logic
In Peter {Stone} and Gerhard {Weiss}, eds., Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'06), 137--144, 2006. Association for Computing Machinery (ACM)

Details
Bibtex

KurzfassungAbstract
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 public 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 succinct in PAL than in EL. This shows
 that, despite the known fact that PAL and EL have the same
 expressive power, there is a benefit in adding the public
 announcement operator to EL: it exponentially increases the
 succinctness of formulas without having negative effects on

computational complexity.

Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ Lutz-AAMAS-06,
  author = {C. {Lutz}},
  booktitle = {Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'06)},
  editor = {Peter {Stone} and Gerhard {Weiss}},
  pages = {137--144},
  publisher = {Association for Computing Machinery (ACM)},
  title = {Complexity and Succinctness of Public Announcement Logic},
  year = {2006},
}