Abstract
In this paper we introduce public announcements to Subset Space Logic (SSL). In order to do this we have to change the original semantics for SSL a little and consider a weaker version of SSL without the cross axiom. We present an axiomatization, prove completeness and show that this logic is PSPACE-complete. Finally, we add the arbitrary announcement modality which expresses “true after any announcement”, prove several semantic results, and show completeness for a Hilbert-style axiomatization of this logic.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Wáng, Y.N., Ågotnes, T.: Subset Space Public Announcement Logic. In: Lodaya, K. (ed.) ICLA 2013. LNCS, vol. 7750, pp. 244–256. Springer, Heidelberg (2013)
Balbiani, P., Baltag, A., van Ditmarsch, H., Herzig, A., Hoshi, T., de Lima, T.: ‘Knowable’ as ‘known after an announcement’. The Review of Symbolic Logic 1, 305–334 (2008)
Başkent, C.: Topics in Subset Space Logic. Master Thesis of the Universiteit van Amsterdam (2007)
Başkent, C.: Public Announcement Logic in Geometric Frameworks. Fundamenta Informaticae 114, 1–17 (2012)
Blackburn, P., de Rijke, M., Venema, Y.: Modal Logic. Cambridge University Press (2001)
Dabrowski, A., Moss, L., Parikh, R.: Topological reasoning and the logic of knowledge. Annals of Pure and Applied Logic 78, 73–110 (1996)
Van Ditmarsch, H., van der Hoek, W., Kooi, B.: Dynamic Epistemic Logic. Springer (2007)
Van Ditmarsch, H., Ruan, J., Verbrugge, R.: Sum and product in dynamic epistemic logic. Journal of Logic and Computation 18, 563–588 (2008)
French, T., Van Ditmarsch, H.: Undecidability for arbitrary public announcement logic. In: Advances in Modal Logic, pp. 23–42 (2008)
Goldblatt, R.: Logics of Time and Computation. Center for the Study of Language and Computation (1992)
Halpern, J.: The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic. Artificial Intelligence 65, 361–372 (1995)
Heinemann, B.: Regarding overlaps in topologic. In: AiML, vol. 6. Kings College Publications, London (2006)
Heinemann, B.: Topology and Knowledge of Multiple Agents. In: Geffner, H., Prada, R., Machado Alexandre, I., David, N. (eds.) IBERAMIA 2008. LNCS (LNAI), vol. 5290, pp. 1–10. Springer, Heidelberg (2008)
Kurucz, A.: Combining modal logics. In: Blackburn, P., van Benthem, J., Wolter, F. (eds.) Handbook of Modal Logic, pp. 869–924. Elsevier (2007)
Lutz, C.: Complexity and succinctness of public announcement logic. In: AAMAS, pp. 137–143 (2006)
Papadimitriou, C.: Computational Complexity. Addison-Wesley (1994)
Parikh, R., Moss, L., Steinsvold, C.: Topology and epistemic logic. In: Handbook of Spatial Logics, pp. 299–341. Springer (2007)
Plaza, J.: Logics of public communications. Synthese 158, 165–179 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Balbiani, P., van Ditmarsch, H., Kudinov, A. (2013). Subset Space Logic with Arbitrary Announcements. In: Lodaya, K. (eds) Logic and Its Applications. ICLA 2013. Lecture Notes in Computer Science, vol 7750. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36039-8_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-36039-8_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36038-1
Online ISBN: 978-3-642-36039-8
eBook Packages: Computer ScienceComputer Science (R0)