research-article

The synchronicity of dynamic epistemic logic

Authors:

Cédric Dégremont,

Benedikt Löwe,

Andreas WitzelAuthors Info & Claims

TARK XIII: Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge

Pages 145 - 152

https://doi.org/10.1145/2000378.2000395

Published: 12 July 2011 Publication History

Abstract

In a recent paper, van Benthem, Gerbrandy, Hoshi and Pacuit gave a natural translation of dynamic epistemic logic (DEL) into epistemic temporal logic (ETL) and proved a representation theorem, characterizing those ETL models that are translations of some DEL protocol; among the characterizing properties we also find synchronicity. In this paper, we argue that synchronicity is not an inherent property of DEL, but rather of the translation that van Benthem et al. used. We provide a different translation that produces asynchronous ETL models and discuss a minimal temporal extension of DEL that removes the ambiguities between the possible translations. This allows us a first attempt at assessing which of the epistemic-temporal properties are intrinsic to DEL and which are properties of the translation.

References

[1]

Guillaume Aucher. Perspectives on Belief and Change. PhD thesis, Université de Toulouse & University of Otago, 2008.

[2]

Alexandru Baltag and Sonja Smets. Dynamic belief revision over multi-agent plausibility models. In G. Bonanno, W. van der Hoek, and M. Wooldridge, editors, Logic and the Foundations of Game and Decision Theory (LOFT 7), volume 3 of Texts in Logic and Games, pages 11--24. Amsterdam University Press, 2006.

[3]

Alexandru Baltag, Lawrence S. Moss, and Slawomir Solecki. The logic of public announcements, common knowledge, and private suspicions. In Itzhak Gilboa, editor, Proceedings of the 7th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-98), pages 43--56, San Francisco, CA, USA, 1998. Morgan Kaufmann Publishers Inc.

Digital Library

[4]

Oliver Board. Dynamic interactive epistemology. Games and Economic Behavior, 49:49--80, 2004.

[5]

Cédric Dégremont. The Temporal Mind. Observations on the Logic of Belief Change in Interactive Systems. PhD thesis, Universiteit van Amsterdam, 2010. ILLC Publications DS-2010-03.

[6]

Ronald Fagin, Joseph Y. Halpern, Moshe Y. Vardi, and Yoram Moses. Reasoning About Knowledge. MIT Press, Cambridge, 1995.

Digital Library

[7]

Joseph Y. Halpern, Ron van der Meyden, and Moshe Y. Vardi. Complete axiomatizations for reasoning about knowledge and time. SIAM Journal on Computing, 33 (3):674--703, 2004.

Digital Library

[8]

Tomohiro Hoshi. Epistemic Dynamics and Protocol Information. PhD thesis, Stanford University, 2009. ILLC Publications DS-2009-08.

Digital Library

[9]

Alistair Isaac and Tomohiro Hoshi. Synchronizing diachronic uncertainty. Journal of Logic, Language and Information, to appear.

Digital Library

[10]

Fenrong Liu. Changing for the Better: Preference Dynamics and Agent Diversity. PhD thesis, Universiteit van Amsterdam, 2008. ILLC Publications DS-2008-02.

[11]

Martin J. Osborne and Ariel Rubinstein. A Course in Game Theory. MIT Press, 1994.

[12]

Rohit Parikh and Ramaswamy Ramanujam. A knowledge based semantics of messages. Journal of Logic, Language and Information, 12(4):453--467, 2003.

Digital Library

[13]

Bryan Renne, Joshua Sack, and Audrey Yap. Dynamic epistemic temporal logic. In Xiangdong He, John Horty, and Eric Pacuit, editors, Proceedings of Logic, Rationality, and Interaction, Second International Workshop (LORI 2009), volume 5834 of Lecture Notes in Artificial Intelligence, pages 263--277. Springer, 2009.

[14]

Joshua Sack. Adding Temporal Logic to Dynamic Epistemic Logic. PhD thesis, Indiana University, 2007.

Digital Library

[15]

Johan van Benthem. Games in Dynamic Epistemic Logic. Bulletin of Economic Research, 53(4):219--248, 2001.

[16]

Johan van Benthem. One is a lonely number. In Z. Chatzidakis, P. Koepke, and W. Pohlers, editors, Proceedings of Logic Colloquium '02, volume 27 of Lecture Notes in Logic, Wellesley MA, 2006. ASL & A. K. Peters.

[17]

Johan van Benthem. Dynamic logic for belief revision. Journal of Applied Non-classical Logics, 17(2), 2007.

[18]

Johan van Benthem and Cédric Dégremont. Bridges between dynamic doxastic and doxastic temporal logics. In Giacomo Bonanno, Benedikt Löwe, and Wiebe van der Hoek, editors, Logic and the Foundations of Game and Decision Theory (LOFT 8), volume 6006 of Lecture Notes in Artificial Intelligence, pages 151--173. Springer, 2010.

Digital Library

[19]

Johan van Benthem, Jan van Eijck, and Barteld Kooi. Logics of communication and change. Information and Computation, 204(11):1620--1662, 2006.

Digital Library

[20]

Johan van Benthem, Jelle Gerbrandy, Tomohiro Hoshi, and Eric Pacuit. Merging frameworks for interaction. Journal of Philosophical Logic, 38(5):491--526, 2009.

[21]

Wiebe van der Hoek and Michael Wooldridge. Cooperation, knowledge, and time: Alternating-time temporal epistemic logic and its applications. Studia Logica, 75(1):125--157, 2003.

[22]

Hans van Ditmarsch. Prolegomena to dynamic logic for belief revision. Synthese, 147:229--275, 2005.

[23]

Hans van Ditmarsch, Wiebe van der Hoek, and Barteld Kooi. Dynamic Epistemic Logic. Springer, 2007.

Digital Library

[24]

Yanjing Wang, Floor Sietsma, and Jan van Eijck. Logic of information flow on communication channels (extended abstract). In Wiebe van der Hoek, Gal A. Kaminka, Yves Lespérance, Michael Luck, and Sandip Sen, editors, Proceedings of the 9th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2010), pages 1447--1448, 2010.

Digital Library

[25]

Yanjing Wang, Floor Sietsma, and Jan van Eijck. Logic of information flow on communication channels. In Andrea Omicini, Sebastian Sardina, and Wamberto Vasconcelos, editors, Declarative Agent Languages and Technologies VIII, volume 6619 of Lecture Notes in Computer Science, pages 130--147. Springer Berlin/Heidelberg, 2011.

Digital Library

[26]

Andreas Witzel. Characterizing perfect recall using next-step temporal operators in S5 Epistemic Temporal Logic. Journal of Logic and Computation, to appear.

Digital Library

Cited By

van Ditmarsch HKuznets R(2024)Wanted dead or alive: epistemic logic for impure simplicial complexesJournal of Logic and Computation10.1093/logcom/exae055Online publication date: 7-Oct-2024
https://doi.org/10.1093/logcom/exae055
van Ditmarsch HKuznets RRandrianomentsoa R(2023)On Two- and Three-valued Semantics for Impure Simplicial ComplexesElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.390.4390(50-66)Online publication date: 30-Sep-2023
https://doi.org/10.4204/EPTCS.390.4
Castañeda Avan Ditmarsch HRosenblueth DVelázquez D(2023)Communication Pattern Logic: Epistemic and Topological ViewsJournal of Philosophical Logic10.1007/s10992-023-09713-8Online publication date: 28-Jul-2023
https://doi.org/10.1007/s10992-023-09713-8
Show More Cited By

Index Terms

The synchronicity of dynamic epistemic logic
1. Theory of computation
  1. Logic
    1. Modal and temporal logics
  2. Models of computation
    1. Computability

Recommendations

Dynamic Epistemic Logic with Communication Actions
Abstract
This work proposes a Dynamic Epistemic Logic with Communication Actions that can be performed concurrently. Unlike Concurrent Epistemic Action Logic introduced by Ditmarsch, Hoek and Kooi [van Ditmarsch, H., W. van der Hoek and B. Kooi, “...
A Succinct Language for Dynamic Epistemic Logic
AAMAS '17: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems

Dynamic epistemic logic (DEL) is an extension of modal multi-agent epistemic logic with dynamic operators. We propose a succinct version of DEL where Kripke models and event models are described succinctly. Our proposal relies on Dynamic logic of ...
Schematic validity in dynamic epistemic logic: decidability
LORI'11: Proceedings of the Third international conference on Logic, rationality, and interaction

Unlike standard modal logics, many dynamic epistemic logics are not closed under uniform substitution. The classic example is Public Announcement Logic (PAL), an extension of epistemic logic based on the idea of information acquisition as elimination of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

TARK XIII: Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge

July 2011

270 pages

ISBN:9781450307079

DOI:10.1145/2000378

Conference Chair:
Krzysztof R. Apt
CWI and University of Amsterdam

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Eruopean Commission
Nederlandse Organisatie voor Wetenschappelijk Onderzoek

Conference

TARK XIII

TARK XIII: Thirteenth conference on Theoretical Aspects of Rationality and Knowledge

July 12 - 14, 2011

Groningen, The Netherlands

Acceptance Rates

Overall Acceptance Rate 61 of 177 submissions, 34%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
140
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

van Ditmarsch HKuznets R(2024)Wanted dead or alive: epistemic logic for impure simplicial complexesJournal of Logic and Computation10.1093/logcom/exae055Online publication date: 7-Oct-2024
https://doi.org/10.1093/logcom/exae055
van Ditmarsch HKuznets RRandrianomentsoa R(2023)On Two- and Three-valued Semantics for Impure Simplicial ComplexesElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.390.4390(50-66)Online publication date: 30-Sep-2023
https://doi.org/10.4204/EPTCS.390.4
Castañeda Avan Ditmarsch HRosenblueth DVelázquez D(2023)Communication Pattern Logic: Epistemic and Topological ViewsJournal of Philosophical Logic10.1007/s10992-023-09713-8Online publication date: 28-Jul-2023
https://doi.org/10.1007/s10992-023-09713-8
Balbiani Pvan Ditmarsch HGonzález S(2022)Asynchronous AnnouncementsACM Transactions on Computational Logic10.1145/348180623:2(1-38)Online publication date: 11-Feb-2022
https://dl.acm.org/doi/10.1145/3481806
Ditmarsch HGoubault ÉLedent JRajsbaum S(2022)Knowledge and Simplicial ComplexesPhilosophy of Computing10.1007/978-3-030-75267-5_1(1-50)Online publication date: 5-May-2022
https://doi.org/10.1007/978-3-030-75267-5_1
van Ditmarsch H(2021)Wanted Dead or Alive: Epistemic Logic for Impure Simplicial ComplexesLogic, Language, Information, and Computation10.1007/978-3-030-88853-4_3(31-46)Online publication date: 6-Oct-2021
https://doi.org/10.1007/978-3-030-88853-4_3
Goubault ÉLedent JRajsbaum S(2020)A simplicial complex model for dynamic epistemic logic to study distributed task computabilityInformation and Computation10.1016/j.ic.2020.104597(104597)Online publication date: Jun-2020
https://doi.org/10.1016/j.ic.2020.104597
Goubault ÉLedent JRajsbaum S(2018)A Simplicial Complex Model for Dynamic Epistemic Logic to study Distributed Task ComputabilityElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.277.6277(73-87)Online publication date: 7-Sep-2018
https://doi.org/10.4204/EPTCS.277.6
van Ditmarsch Hvan der Hoek WKooi B(2018)Playing Cards with Hintikka: An Introduction to Dynamic Epistemic LogicJaakko Hintikka on Knowledge and Game-Theoretical Semantics10.1007/978-3-319-62864-6_9(237-262)Online publication date: 2-Feb-2018
https://doi.org/10.1007/978-3-319-62864-6_9
KNIGHT SMAUBERT BSCHWARZENTRUBER F(2017)Reasoning about knowledge and messages in asynchronous multi-agent systemsMathematical Structures in Computer Science10.1017/S0960129517000214(1-42)Online publication date: 10-Nov-2017
https://doi.org/10.1017/S0960129517000214
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents