{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:17:32Z","timestamp":1760203052208},"reference-count":50,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2022,3,12]],"date-time":"2022-03-12T00:00:00Z","timestamp":1647043200000},"content-version":"vor","delay-in-days":1,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,8,24]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Arbitrary public announcement logic (APAL) is a logic of change of knowledge with modalities representing quantification over announcements. We present two rather different versions of APAL wherein this quantification is restricted to formulas only containing a subset of all propositional variables: SAPAL and SCAPAL. Such restrictions are relevant in principle for the specification of multi-agent system dynamics. We also present another version of APAL, quantifying over all announcements implied by or implying a given formula: IPAL. We then determine the relative expressivity of all these logics and APAL. We also present complete axiomatizations of SAPAL and SCAPAL and show undecidability of satisfiability for all logics involved, by arguments nearly identical to those for APAL. We show that the IPAL quantifier, motivated by the satisfaction clause for substructural implication, yields a new substructural dynamic consequence relation.<\/jats:p>","DOI":"10.1093\/logcom\/exac012","type":"journal-article","created":{"date-parts":[[2022,2,14]],"date-time":"2022-02-14T20:26:26Z","timestamp":1644870386000},"page":"1350-1378","source":"Crossref","is-referenced-by-count":0,"title":["Almost APAL"],"prefix":"10.1093","volume":"33","author":[{"given":"Hans","family":"van Ditmarsch","sequence":"first","affiliation":[{"name":"Open University , the Netherlands, PO Box 2960, 6401 DL Heerlen, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mo","family":"Liu","sequence":"additional","affiliation":[{"name":"CNRS, LORIA , University of Lorraine, BP 239 54506 Vandoeuvre-l\u00e8s-Nancy, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Louwe B","family":"Kuijer","sequence":"additional","affiliation":[{"name":"University of Liverpool , Ashton Street Liverpool, L69 3BX, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Sedlar","sequence":"additional","affiliation":[{"name":"Institute of Computer Science , Czech Academy of Sciences, Pod Vod\u00e1renskou v\u011b\u017e\u00ed 271\/2 182 07 Praha 8, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,3,11]]},"reference":[{"key":"2023090708034766400_ref1","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.jal.2008.12.002","article-title":"Group announcement logic","volume":"8","author":"\u00c5gotnes","year":"2010","journal-title":"Journal of Applied Logic"},{"key":"2023090708034766400_ref2","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/s11225-016-9657-0","article-title":"The undecidability of quantified announcements","volume":"104","author":"\u00c5gotnes","year":"2016","journal-title":"Studia Logica"},{"key":"2023090708034766400_ref3","doi-asserted-by":"crossref","first-page":"855","DOI":"10.1007\/978-3-319-06025-5_33","article-title":"Dynamic epistemic logic as a substructural logic","volume-title":"Johan van Benthem on Logic and Information Dynamics","author":"Aucher","year":"2014"},{"key":"2023090708034766400_ref4","doi-asserted-by":"crossref","first-page":"1913","DOI":"10.1093\/logcom\/exw002","article-title":"Dynamic epistemic logic in update logic","volume":"26","author":"Aucher","year":"2016","journal-title":"Journal of Logic and Computation"},{"key":"2023090708034766400_ref5","first-page":"27","article-title":"Undecidability in epistemic planning","volume-title":"Proc. of 23rd IJCAI","author":"Aucher","year":"2013"},{"key":"2023090708034766400_ref6","doi-asserted-by":"crossref","first-page":"1236","DOI":"10.1214\/aos\/1176343654","article-title":"Agreeing to disagree","volume":"4","author":"Aumann","year":"1976","journal-title":"Annals of Statistics"},{"key":"2023090708034766400_ref7","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1080\/11663081.2015.1011489","article-title":"Putting right the wording and the proof of the Truth Lemma for APAL","volume":"25","author":"Balbiani","year":"2015","journal-title":"Journal of Applied Non-Classical Logics"},{"key":"2023090708034766400_ref8","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1017\/S1755020308080210","article-title":"Knowable\u2019 as \u2018known after an announcement","volume":"1","author":"Balbiani","year":"2008","journal-title":"The Review of Symbolic Logic"},{"key":"2023090708034766400_ref9","first-page":"65","article-title":"A simple proof of the completeness of APAL","volume":"8","author":"Balbiani","year":"2015","journal-title":"Studies in Logic"},{"key":"2023090708034766400_ref10","first-page":"43","article-title":"The logic of public announcements, common knowledge, and private suspicions","volume-title":"Proc. of 7th TARK","author":"Baltag","year":"1998"},{"key":"2023090708034766400_ref11","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1007\/978-3-662-57669-4_6","article-title":"APAL with memory is better","volume-title":"Logic, Language, Information, and Computation","author":"Baltag","year":"2018"},{"key":"2023090708034766400_ref12","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1007\/s10992-011-9191-5","article-title":"On the ternary relation and conditionality","volume":"41","author":"Beall","year":"2012","journal-title":"Journal of Philosophical Logic"},{"key":"2023090708034766400_ref13","volume-title":"Memoirs of the AMS","author":"Berger","year":"1966"},{"key":"2023090708034766400_ref14","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781107050884","volume-title":"Modal Logic","author":"Blackburn","year":"2001"},{"key":"2023090708034766400_ref15","doi-asserted-by":"crossref","first-page":"9","DOI":"10.3166\/jancl.21.9-34","article-title":"Epistemic planning for single and multi-agent systems","volume":"21","author":"Bolander","year":"2011","journal-title":"Journal of Applied Non-Classical Logics"},{"key":"2023090708034766400_ref16","doi-asserted-by":"crossref","DOI":"10.1016\/j.artint.2020.103304","article-title":"Del-based epistemic planning: Decidability and complexity","volume":"287","author":"Bolander","year":"2020","journal-title":"Artificial Intelligence"},{"key":"2023090708034766400_ref17","first-page":"1471","article-title":"Arbitrary public announcement logic with mental programs","volume-title":"Proc. of AAMAS","author":"Charrier","year":"2015"},{"key":"2023090708034766400_ref18","doi-asserted-by":"crossref","first-page":"654","DOI":"10.1016\/j.disc.2018.10.041","article-title":"The epistemic gossip problem","volume":"342","author":"Cooper","year":"2019","journal-title":"Discrete Mathematics"},{"key":"2023090708034766400_ref19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-94-017-0460-1_1","article-title":"Relevance logic","volume-title":"Handbook of Philosophical Logic","author":"Dunn","year":"2002"},{"key":"2023090708034766400_ref20","first-page":"23","article-title":"Undecidability for arbitrary public announcement logic","volume-title":"Advances in Modal Logic 7","author":"French","year":"2008"},{"key":"2023090708034766400_ref21","volume-title":"Residuated Lattices: An Algebraic Glimpse at Substructural Logics","author":"Galatos","year":"2007"},{"key":"2023090708034766400_ref22","volume-title":"Coalition Announcements","author":"Galimullin","year":"2019"},{"key":"2023090708034766400_ref23","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1023\/A:1008222603071","article-title":"Reasoning about information change","volume":"6","author":"Gerbrandy","year":"1997","journal-title":"Journal of Logic, Language, and Information"},{"key":"2023090708034766400_ref24","volume-title":"Axiomatising the Logic of Computer Programming","author":"Goldblatt","year":"1982"},{"key":"2023090708034766400_ref25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3233\/AIC-170723","article-title":"How to share knowledge by gossiping","volume":"30","author":"Herzig","year":"2017","journal-title":"AI Communications"},{"key":"2023090708034766400_ref26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1080\/00455091.1977.10716173","article-title":"Remarks on personal and impersonal knowledge","volume":"7","author":"Hilpinen","year":"1977","journal-title":"Canadian Journal of Philosophy"},{"key":"2023090708034766400_ref27","volume-title":"Knowledge and Belief","author":"Hintikka","year":"1962"},{"key":"2023090708034766400_ref28","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1317379.1317381","article-title":"Gossiping in distributed systems","volume":"41","author":"Kermarrec","year":"2007","journal-title":"SIGOPS Operating Systems Review"},{"key":"2023090708034766400_ref29","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511805318","volume-title":"Distributed Computing: Principles, Algorithms, and Systems","author":"Kshemkalyani","year":"2008"},{"key":"2023090708034766400_ref30","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/978-3-662-44116-9_8","article-title":"How arbitrary are arbitrary public announcements?","volume-title":"Pristine Perspectives on Logic, Language and Computation","author":"Kuijer","year":"2014"},{"key":"2023090708034766400_ref31","first-page":"47","article-title":"Information-theoretic cryptography","volume-title":"Advances in Cryptology\u2014CRYPTO \u201899, LNCS 1666","author":"Maurer","year":"1999"},{"key":"2023090708034766400_ref32","article-title":"Formalization of two puzzles involving knowledge","volume-title":"Formalizing Common Sense: Papers by John McCarthy","author":"McCarthy","year":"1990"},{"key":"2023090708034766400_ref33","first-page":"535","article-title":"A reply to my critics","volume-title":"The Philosophy of G.E. Moore","author":"Moore","year":"1942"},{"key":"2023090708034766400_ref34","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF01661170","article-title":"Cheating husbands and other stories: a case study of knowledge, action, and communication","volume":"1","author":"Moses","year":"1986","journal-title":"Distributed Computing"},{"key":"2023090708034766400_ref35","doi-asserted-by":"crossref","DOI":"10.1007\/978-94-017-3179-9","volume-title":"Substructural Logics: A Primer","author":"Paoli","year":"2002"},{"key":"2023090708034766400_ref36","first-page":"201","article-title":"Logics of public communications","volume-title":"Proc. of the 4th ISMIS","author":"Plaza","year":"1989"},{"key":"2023090708034766400_ref37","article-title":"Information based reasoning about security protocols","volume":"55","author":"Ramanujam","year":"2001","journal-title":"Electronic Notes in Theoretical Computer Science"},{"key":"2023090708034766400_ref38","doi-asserted-by":"crossref","DOI":"10.4324\/9780203252642","volume-title":"An Introduction to Substructural Logics","author":"Restall","year":"2000"},{"key":"2023090708034766400_ref39","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/S1874-5857(06)80030-0","article-title":"Relevant and substructural logics","volume-title":"Logic and the Modalities in the Twentieth Century","author":"Restall","year":"2006"},{"key":"2023090708034766400_ref40","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1016\/S0049-237X(08)71541-6","article-title":"Semantics of entailment","volume-title":"Truth, Syntax and Modality","author":"Routley","year":"1973"},{"key":"2023090708034766400_ref41","volume":"1","author":"Routley","year":"1982","journal-title":"Relevant Logics and Their Rivals"},{"key":"2023090708034766400_ref42","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198537779.001.0001","volume-title":"Substructural Logics","author":"Schr\u00f6der-Heister","year":"1993"},{"key":"2023090708034766400_ref43","doi-asserted-by":"crossref","DOI":"10.1016\/S0049-237X(08)70133-2","article-title":"Semantic parallels in natural language and computation","volume-title":"Logic Colloquium \u201987, Proceedings of the Colloquium held in Granada","author":"van Benthem","year":"1989"},{"key":"2023090708034766400_ref44","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1163\/9789004454149_004","article-title":"Structural properties of dynamic reasoning","volume-title":"Meaning: The Dynamic Turn","author":"van Benthem","year":"2003"},{"key":"2023090708034766400_ref45","doi-asserted-by":"crossref","first-page":"182","DOI":"10.26686\/ajl.v6i0.1801","article-title":"Logical dynamics meets logical pluralism","volume":"6","author":"van Benthem","year":"2008","journal-title":"Australasian Journal of Logic"},{"key":"2023090708034766400_ref46","first-page":"20","article-title":"Quantifying over Boolean announcements","volume":"18","author":"van Ditmarsch","year":"2022","journal-title":"Logical Methods in Computer Science"},{"key":"2023090708034766400_ref47","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1007\/s11225-020-09922-1","article-title":"Positive announcements","volume":"109","author":"van Ditmarsch","year":"2021","journal-title":"Studia Logica"},{"key":"2023090708034766400_ref48","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/s11229-005-3384-9","article-title":"The secret of my success","volume":"151","author":"van Ditmarsch","year":"2006","journal-title":"Synthese"},{"key":"2023090708034766400_ref49","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1007\/978-3-030-65840-3_8","article-title":"Expressivity of some versions of APAL","volume-title":"Dynamic Logic. New Trends and Applications","author":"van Ditmarsch","year":"2020"},{"key":"2023090708034766400_ref50","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1515\/9783110867602.159","article-title":"The Conway paradox: its solution in an epistemic framework","volume-title":"Truth, Interpretation and Information: Selected Papers From the Third Amsterdam Colloquium","author":"van Emde Boas","year":"1984"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/33\/6\/1350\/51402201\/exac012.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/33\/6\/1350\/51402201\/exac012.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,17]],"date-time":"2023-11-17T13:24:21Z","timestamp":1700227461000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/33\/6\/1350\/6546900"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,11]]},"references-count":50,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2022,3,11]]},"published-print":{"date-parts":[[2023,8,24]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exac012","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,9]]},"published":{"date-parts":[[2022,3,11]]}}}