Automata Techniques for Epistemic Protocol Synthesis

Guillaume Aucher
Bastien Maubert
Sophie Pinchinat

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.

In Fabio Mogavero, Aniello Murano and Moshe Y. Vardi: Proceedings 2nd International Workshop on Strategic Reasoning (SR 2014), Grenoble, France, April 5-6, 2014, Electronic Proceedings in Theoretical Computer Science 146, pp. 97–103.
Published: 1st April 2014.

ArXived at: https://dx.doi.org/10.4204/EPTCS.146.13 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org