{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T06:14:52Z","timestamp":1776665692872,"version":"3.51.2"},"reference-count":46,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2017,11,10]],"date-time":"2017-11-10T00:00:00Z","timestamp":1510272000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>We propose a variant of public announcement logic for asynchronous systems. To capture asynchrony, we introduce two different modal operators for sending and receiving messages. The natural approach to defining the semantics leads to a circular definition, but we describe two restricted cases in which we solve this problem. The first case requires the Kripke model representing the initial epistemic situation to be a finite tree, and the second one only allows announcements from the existential fragment. After establishing some validities, we study the model checking problem and the satisfiability problem in cases where the semantics is well-defined, and we provide several complexity results.<\/jats:p>","DOI":"10.1017\/s0960129517000214","type":"journal-article","created":{"date-parts":[[2017,11,10]],"date-time":"2017-11-10T11:33:46Z","timestamp":1510313626000},"page":"127-168","source":"Crossref","is-referenced-by-count":7,"title":["Reasoning about knowledge and messages in asynchronous multi-agent systems"],"prefix":"10.1017","volume":"29","author":[{"given":"SOPHIA","family":"KNIGHT","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BASTIEN","family":"MAUBERT","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"FRAN\u00c7OIS","family":"SCHWARZENTRUBER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2017,11,10]]},"reference":[{"key":"S0960129517000214_ref46","doi-asserted-by":"publisher","DOI":"10.1002\/rnc.592"},{"key":"S0960129517000214_ref41","doi-asserted-by":"crossref","unstructured":"van Ditmarsch H. , van der Hoek W. and Kooi B.P. (2007). Dynamic Epistemic Logic, Vol. 337.","DOI":"10.1007\/978-1-4020-5839-4"},{"key":"S0960129517000214_ref39","unstructured":"van Ditmarsch H. (2017). Asynchronous announcements. CoRR abs\/1705.03392. http:\/\/arxiv.org\/abs\/1705.03392"},{"key":"S0960129517000214_ref26","volume-title":"Einf\u00fchrung in die Intensionale Semantik","author":"Kutschera","year":"1976"},{"key":"S0960129517000214_ref43","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13824-9_7"},{"key":"S0960129517000214_ref19","first-page":"1","article-title":"Big brother logic: Visual-epistemic reasoning in stationary multi-agent systems","volume":"30","author":"Gasquet","year":"2015","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"key":"S0960129517000214_ref10","unstructured":"Bra\u00fcner T. , Blackburn P. and Polyanskaya I. (2016). Second-order false-belief tasks: Analysis and formalization. In: Proceedings of the Logic, Language, Information, and Computation - 23rd International Workshop, WoLLIC 2016, Puebla, Mexico, August 16\u201319th, 2016, 125\u2013 144."},{"key":"S0960129517000214_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85361-9_28"},{"key":"S0960129517000214_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-51726-5.50015-7"},{"key":"S0960129517000214_ref28","first-page":"1","article-title":"Recent work in epistemic logic","volume":"30","author":"Lenzen","year":"1978","journal-title":"Acta Philosophica Fennica"},{"key":"S0960129517000214_ref34","first-page":"35","article-title":"The complexity of temporal logic model checking","volume":"4","author":"Schnoebelen","year":"2002","journal-title":"Advances in Modal Logic"},{"key":"S0960129517000214_ref4","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exn060"},{"key":"S0960129517000214_ref33","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38123-2"},{"key":"S0960129517000214_ref18","unstructured":"French T. and van Ditmarsch H. P. (2008). Undecidability for arbitrary public announcement logic. In: Proceedings of the AiML '08."},{"key":"S0960129517000214_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762112"},{"key":"S0960129517000214_ref13","unstructured":"Charrier T. and Schwarzentruber F. (2017). Arbitrary public announcement logic with mental programs. In: Proceedings of the 2017 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2017 (to appear)."},{"key":"S0960129517000214_ref38","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0018447"},{"key":"S0960129517000214_ref27","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"S0960129517000214_ref42","unstructured":"van Emde Boas P. (1997). The convenience of tilings. Lecture Notes in Pure and Applied Mathematics."},{"key":"S0960129517000214_ref29","doi-asserted-by":"crossref","unstructured":"Lutz C. (2006). Complexity and succinctness of public announcement logic. In: Proceedings of the AAMAS '06.","DOI":"10.1145\/1160633.1160657"},{"key":"S0960129517000214_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511974533"},{"key":"S0960129517000214_ref20","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008222603071"},{"key":"S0960129517000214_ref17","doi-asserted-by":"publisher","DOI":"10.1145\/128749.150945"},{"key":"S0960129517000214_ref9","doi-asserted-by":"publisher","DOI":"10.1145\/322374.322380"},{"key":"S0960129517000214_ref14","doi-asserted-by":"crossref","unstructured":"Corradini F. , Berardini M.R.D. and Vogler W. (2003). Relating fairness and timing in process algebras. In: Proceedings of the CONCUR '03.","DOI":"10.1007\/978-3-540-45187-7_29"},{"key":"S0960129517000214_ref35","volume-title":"Introduction to the Theory of Computation","author":"Sipser","year":"1997"},{"key":"S0960129517000214_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38592-6_10"},{"key":"S0960129517000214_ref1","unstructured":"Aucher G. and Schwarzentruber F. (2013). On the complexity of dynamic epistemic logic. In: TARK '13."},{"key":"S0960129517000214_ref12","unstructured":"Charrier T. and Schwarzentruber F. (2015). Arbitrary public announcement logic with mental programs. In: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015, Istanbul, Turkey, May 4\u20138, 2015, 1471\u20131479. http:\/\/dl.acm.org\/citation.cfm?id=2773340"},{"key":"S0960129517000214_ref25","doi-asserted-by":"crossref","unstructured":"Knight S. , Maubert B. and Schwarzentruber F. (2015). Asynchronous announcements in a public channel. In: Proceedings of the ICTAC '15.","DOI":"10.1007\/978-3-319-25150-9_17"},{"key":"S0960129517000214_ref37","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48561-3_30"},{"key":"S0960129517000214_ref3","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/jzs052"},{"key":"S0960129517000214_ref45","doi-asserted-by":"crossref","first-page":"2514","DOI":"10.1109\/TCOM.1982.1095450","article-title":"Deadlock detection for a class of communicating finite state machines","volume":"30","author":"Yu","year":"1982","journal-title":"IEEE Transactions on Communications"},{"key":"S0960129517000214_ref22","doi-asserted-by":"publisher","DOI":"10.1145\/79147.79161"},{"key":"S0960129517000214_ref16","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/5803.001.0001","volume-title":"Reasoning About Knowledge","author":"Fagin","year":"2004"},{"key":"S0960129517000214_ref2","unstructured":"Balbiani P. , Baltag A. , van Ditmarsch H.P. , Herzig A. , Hoshi T. and Lima T.D. (2007). What can we achieve by arbitrary announcements?: A dynamic take on Fitch's knowability. In: TARK '07."},{"key":"S0960129517000214_ref24","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.polisci.2.1.297"},{"key":"S0960129517000214_ref6","doi-asserted-by":"publisher","DOI":"10.1023\/B:SYNT.0000024912.56773.5e"},{"key":"S0960129517000214_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/BF02252679"},{"key":"S0960129517000214_ref7","unstructured":"Baltag A. , Moss L.S. and Solecki S. (1998). The logic of public announcements and common knowledge and private suspicions. In: Proceedings of the 7th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-98), Evanston, IL, USA, July 22\u201324, 1998, 43\u2013 56."},{"key":"S0960129517000214_ref23","volume-title":"Knowledge and Belief: An Introduction to the Logic of the Two Notions","author":"Hintikka","year":"1962"},{"key":"S0960129517000214_ref44","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3054.001.0001","volume-title":"The Formal Semantics of Programming Languages - An Introduction","author":"Winskel","year":"1993"},{"key":"S0960129517000214_ref15","unstructured":"D\u00e9gremont C. , L\u00f6we B. and Witzel A. (2011). The synchronicity of dynamic epistemic logic. In: Proceedings of the TARK '11."},{"key":"S0960129517000214_ref40","unstructured":"van Ditmarsch H. , French T. and Hales J. Positive announcements (submitted)."},{"key":"S0960129517000214_ref36","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1955.5.285"},{"key":"S0960129517000214_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/s11229-007-9168-7"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129517000214","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,21]],"date-time":"2020-10-21T15:21:09Z","timestamp":1603293669000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129517000214\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,10]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["S0960129517000214"],"URL":"https:\/\/doi.org\/10.1017\/s0960129517000214","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11,10]]}}}