Strategic Reasoning Under Imperfect Information with Synchronous Semantics (Invited Talk)

File

Author Details

Sophie Pinchinat

IRISA Laboratory/University of Rennes, France

Cite As Get BibTex

Sophie Pinchinat. Strategic Reasoning Under Imperfect Information with Synchronous Semantics (Invited Talk). In 31st International Symposium on Temporal Representation and Reasoning (TIME 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 318, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024) https://doi.org/10.4230/LIPIcs.TIME.2024.2

Abstract

Dynamic Epistemic Logic is a modal logic dedicated to specifying epistemic property changes along the dynamic behavior of a multi-agent system. The models that underlie this logic are (epistemic) states together with transitions caused by events, the occurrence of which may modify the current state. We first develop a setting where the entire dynamics of the system starting from an initial state is captured by a single infinite tree, in a way similar to what has been considered for Epistemic Temporal Logic, and second go through the current state-of-the-art regarding strategic reasoning, with a focus on planning problems in this infinite structure.

Subject Classification

ACM Subject Classification

Theory of computation → Formal languages and automata theory
Theory of computation → Logic and verification
Theory of computation → Modal and temporal logics
Theory of computation → Verification by model checking

Keywords

Strategic reasoning
Imperfect information
chain-MSO
Automatic structures

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Achim Blumensath and Erich Grädel. Automatic structures. In Logic in Computer Science, 2000. Proceedings. 15th Annual IEEE Symposium on, pages 51-62. IEEE, 2000. URL: https://doi.org/10.1109/LICS.2000.855755.
Thomas Bolander, Tristan Charrier, Sophie Pinchinat, and François Schwarzentruber. Del-based epistemic planning: Decidability and complexity. Artif. Intell., 287:103304, 2020. URL: https://doi.org/10.1016/j.artint.2020.103304.
Gaëtan Douéneau-Tabot, Sophie Pinchinat, and François Schwarzentruber. Chain-monadic second order logic over regular automatic trees and epistemic planning synthesis. In Guram Bezhanishvili, Giovanna D'Agostino, George Metcalfe, and Thomas Studer, editors, Advances in Modal Logic 12, proceedings of the 12th conference on "Advances in Modal Logic," held in Bern, Switzerland, August 27-31, 2018, pages 237-256. College Publications, 2018. URL: http://www.aiml.net/volumes/volume12/DoueneauTabot-Pinchinat-Schwarzentruber.pdf.
Bakhadyr Khoussainov and Anil Nerode. Automatic presentations of structures. In Logic and computational complexity, pages 367-392. Springer, 1995.
Bastien Maubert. Logical foundations of games with imperfect information: uniform strategies. PhD thesis, Université Rennes 1, 2014.
Bastien Maubert, Aniello Murano, Sophie Pinchinat, François Schwarzentruber, and Silvia Stranieri. Dynamic epistemic logic games with epistemic temporal goals. In Giuseppe De Giacomo, Alejandro Catalá, Bistra Dilkina, Michela Milano, Senén Barro, Alberto Bugarín, and Jérôme Lang, editors, ECAI 2020 - 24th European Conference on Artificial Intelligence, 29 August-8 September 2020, Santiago de Compostela, Spain, August 29 - September 8, 2020 - Including 10th Conference on Prestigious Applications of Artificial Intelligence (PAIS 2020), volume 325 of Frontiers in Artificial Intelligence and Applications, pages 155-162. IOS Press, 2020. URL: https://doi.org/10.3233/FAIA200088.
Bastien Maubert, Sophie Pinchinat, François Schwarzentruber, and Silvia Stranieri. Concurrent games in dynamic epistemic logic. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 1877-1883. ijcai.org, 2020. URL: https://doi.org/10.24963/ijcai.2020/260.
Côme Neyrand and Sophie Pinchinat. On the role of postconditions in dynamic first-order epistemic logic. CoRR, abs/2205.00876, 2022. URL: https://doi.org/10.48550/arXiv.2205.00876.
Michael O Rabin. Decidability of second-order theories and automata on infinite trees. Transactions of the american Mathematical Society, 141:1-35, 1969.
Wolfgang Thomas. Infinite trees and automaton-definable relations over ω-words. Theoretical Computer Science, 103(1):143-159, 1992.
Hans Van Ditmarsch, Wiebe van Der Hoek, and Barteld Kooi. Dynamic epistemic logic, volume 337. Springer Science & Business Media, 2007.