Complexity and Succinctness of Public Announcement Logic
|
Descargar SCORM
¡Sea el primero en solicitar este recurso!
Para poder solicitar este recurso debe identificarse como usuario de la biblioteca
|
| |
Ver
Detalles del recurso
|
|
|
Complexity and Succinctness of Public Announcement Logic
|
| Id. |
47435523 |
| Idioma |
inglés
|
| Titulo |
Complexity and Succinctness of Public Announcement Logic |
| Localización |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.83.5832
|
| Versión |
1.0 |
| Estado |
Final
|
| Descripción |
There is a recent trend of extending epistemic logic (EL) with dynamic operators that allow to express the evolution of knowledge and 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.
|
| Tipo |
application/pdf
|
| Palabras clave |
epistemic logic
|
| Tipo de recurso |
Texto Narrativo
|
| Tipo de Interactividad |
Expositivo
|
| Nivel de Interactividad |
muy bajo
|
| Audiencia |
Estudiante
Profesor
Autor
|
| Estructura |
Atomic |
| Coste |
no
|
| Copyright |
sí
|
|
Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| Formatos |
application/pdf
|
| Requerimientos técnicos |
Browser: Any
|
| Relación |
[IsBasedOn] http://lat.inf.tu-dresden.de/~clu/papers/archive/aamas06.pdf
[References] 10.1.1.101.7942
[References] 10.1.1.12.9588
|
| Fecha de contribución |
03-sep-2009 |
|
|
|
|
Valoración de los usuarios
No hay ninguna valoración para este recurso. Sea el primero en
valorar este recurso.
|
|
|
|
