Skip to Main content Skip to Navigation
Conference papers

Automata Techniques for Epistemic Protocol Synthesis

Guillaume Aucher 1, 2 Bastien Maubert 3 Sophie Pinchinat 4
3 CELLO - Computational Epistemic Logic in LOrraine
LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
4 LogicA - Logic and Applications
ENS Cachan - École normale supérieure - Cachan, UR1 - Université de Rennes 1, IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
Abstract : In this work we aim at applying automata techniques to problems studied in Dynamic Epistemic Logic, such as epistemic planning. To do so, we first remark that repeatedly executing ad infinitum a propositional event model from an initial epistemic model yields a relational structure that can be finitely represented with automata. This correspondence, together with recent results on uniform strategies, allows us to give an alternative decidability proof of the epistemic planning problem for propositional events, with as by-products accurate upper-bounds on its time complexity, and the possibility to synthesize a finite word automaton that describes the set of all solution plans. In fact, using automata techniques enables us to solve a much more general problem, that we introduce and call epistemic protocol synthesis.
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Sophie Pinchinat <>
Submitted on : Monday, September 7, 2015 - 10:46:48 AM
Last modification on : Wednesday, March 10, 2021 - 3:43:33 PM
Long-term archiving on: : Tuesday, December 8, 2015 - 11:40:06 AM


Publisher files allowed on an open archive



Guillaume Aucher, Bastien Maubert, Sophie Pinchinat. Automata Techniques for Epistemic Protocol Synthesis. 2nd International Workshop on Strategic Reasoning, Apr 2014, 2014-04-06, France. pp.11, ⟨10.4204/EPTCS.146.13⟩. ⟨hal-01098740⟩



Record views


Files downloads