Abstract
Arbitrary public announcement logic (\( APAL \)) reasons about how the knowledge of a set of agents changes after true public announcements and after arbitrary announcements of true epistemic formulas. We consider a variant of arbitrary public announcement logic called positive arbitrary public announcement logic (\( APAL ^+\)), which restricts arbitrary public announcements to announcement of positive formulas. Positive formulas prohibit statements about the ignorance of agents. The positive formulas correspond to the universal fragment in first-order logic. As two successive announcements of positive formulas need not correspond to the announcement of a positive formula, \( APAL ^+\) is rather different from \( APAL \). We show that \( APAL ^+\) is more expressive than public announcement logic \( PAL \), and that \( APAL ^+\) is incomparable with \( APAL \). We also provide a sound and complete infinitary axiomatisation.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ågotnes, T., P. Balbiani, H. van Ditmarsch, and P. Seban, Group announcement logic, Journal of Applied Logic 8:62–81, 2010.
Ågotnes, T., H. van Ditmarsch, and T. French, The undecidability of quantified announcements, Studia Logica 104(4):597–640, 2016.
Andréka, H., I. Németi, and J. van Benthem, Modal languages and bounded fragments of predicate logic, Journal of Philosophical Logic 27(3):217–274, 1998.
Balbiani, P., Putting right the wording and the proof of the Truth Lemma for APAL, Journal of Applied Non-Classical Logics 25(1):2–19, 2015.
Balbiani, P., A. Baltag, H. van Ditmarsch, A. Herzig, T. Hoshi, and T. D. Lima, ‘Knowable’ as ‘known after an announcement’, Review of Symbolic Logic 1(3):305–334, 2008.
Balbiani, P., and H. van Ditmarsch, A simple proof of the completeness of APAL, Studies in Logic 8(1):65–78, 2015.
Blackburn, P., M. de Rijke, and Y. Venema, Modal Logic, Cambridge University Press, Cambridge, 2001. Cambridge Tracts in Theoretical Computer Science 53.
Bozzelli, L., H. van Ditmarsch, T. French, J. Hales, and S. Pinchinat, Refinement modal logic, Information and Computation 239:303–339, 2014.
Browne, M., E. Clarke, and O. Grümberg, Characterizing Kripke structures in temporal logic, in H. Ehrig, R. Kowalski, G. Levi, and U. Montanari, (eds.), TAPSOFT ’87, LNCS 249, Springer, 1987, pp. 256–270.
Chandra, A., D. Kozen, and L. Stockmeyer, Alternation, Journal of the ACM 28:114–33, 1981.
Charrier, T., and F. Schwarzentruber, Arbitrary public announcement logic with mental programs, in Proc. of AAMAS, ACM, 2015, pp. 1471–1479.
Chaum, D., The dining cryptographers problem: Unconditional sender and recipient untraceability, J. Cryptol. 1(1):65–75, 1988.
Cordón-Franco, A., H. van Ditmarsch, D. Fernández-Duque, and F. Soler-Toscano, A colouring protocol for the generalized russian cards problem, Theor. Comput. Sci. 495:81–95, 2013.
D’Agostino, G., and M. Hollenberg, Logical questions concerning the \(\mu \)-calculus: Interpolation, Lyndon and Los-Tarski, Journal of Symbolic Logic 65(1):310–332, 2000.
Fischer, M., and R. Wright, Bounds on secret key exchange using a random deal of cards, Journal of Cryptology 9(2):71–99, 1996.
French, T., Bisimulation quantified modal logics: Decidability, in G. Governatori, I. Hodkinson, and Y. Venema, (eds.), Proc. of 6th AiML, College Publications, 2006, pp. 147–166.
French, T., R. Galimullin, H. van Ditmarsch, and N. Alechina, Groups versus coalitions: On the relative expressivity of GAL and CAL, in Proc. of the 18th AAMAS, 2019, pp. 953–961.
French, T., and H. van Ditmarsch, Undecidability for arbitrary public announcement logic, in Advances in Modal Logic 7, College Publications, London, 2008, pp. 23–42.
Galimullin, R., Coalition announcements, Ph.D. thesis, University of Nottingham, UK, 2019.
Gerbrandy, J., and W. Groeneveld, Reasoning about information change, Journal of Logic, Language, and Information 6:147–169, 1997.
Hales, J., Arbitrary action model logic and action model synthesis, in Proc. of 28th LICS. IEEE, 2013, pp. 253–262.
Hales, J., T. French, and R. Davies, Refinement quantified logics of knowledge and belief for multiple agents, in Advances in Modal Logic 9, College Publications, 2012, pp. 317–338.
Halpern, J., and L. Zuck, A little knowledge goes a long way: Knowledge-based derivations and correctness proofs for a family of protocols, J. ACM 39(3):449–478, 1992.
Hennessy, M., and R. Milner, Algebraic laws for nondeterminism and concurrency, J. ACM 32(1):137–161, 1985.
Plaza, J., Logics of public communications, in Proc. of the 4th ISMIS, Oak Ridge National Laboratory, 1989, pp. 201–216.
Stulp, F., and R. Verbrugge, A knowledge-based algorithm for the internet transmission control protocol (TCP), Bulletin of Economic Research 54(1):69–94, 2002.
Swan, M., Blockchain: Blueprint for a New Economy, O’Reilly, Sebastopol, 2015.
van Benthem, J., Dynamic odds and ends. Technical report, University of Amsterdam, 1998. ILLC Research Report ML-1998-08.
van Benthem, J., One is a lonely number: on the logic of communication, in Logic colloquium 2002. Lecture Notes in Logic, Vol. 27. A.K. Peters, 2006, pp. 96–129.
van der Meyden, R., and K. Su, Symbolic model checking the knowledge of the dining cryptographers, in Proc. of the 17th IEEE workshop on Computer Security Foundations, 2004, pp. 280–291.
van Ditmarsch, H., The Russian cards problem, Studia Logica 75:31–62, 2003.
van Ditmarsch, H., D. Fernández-Duque, and W. van der Hoek, On the definability of simulation and bisimulation in epistemic logic, J. Log. Comput. 24(6):1209–1227, 2014.
van Ditmarsch, H., and T. French, Quantifying over boolean announcements. https://arxiv.org/abs/1712.05310, 2017.
van Ditmarsch, H., T. French, and J. Hales, Decidability of arbitrary positive announcement logic, Manuscript, 2018.
van Ditmarsch, H., and B. Kooi, The secret of my success, Synthese 151:201–232, 2006.
van Ditmarsch, H., W. van der Hoek, and L. Kuijer, The undecidability of arbitrary arrow update logic, Theor. Comput. Sci. 693:1–12, 2017.
Acknowledgements
We kindly acknowledge support from ERC project EPS 313360. A preliminary version of this work was presented at the 2014 Software Engineering Research Conference organized by the UWA doctoral school, see http://jameshales.org/manuscripts/csse2014.pdf.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Presented by Yde Venema
Rights and permissions
About this article
Cite this article
van Ditmarsch, H., French, T. & Hales, J. Positive Announcements. Stud Logica 109, 639–681 (2021). https://doi.org/10.1007/s11225-020-09922-1
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11225-020-09922-1