Automata Techniques for Epistemic Protocol Synthesis

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.
Type de document :
Communication dans un congrès
Fabio Mogavero and Aniello Murano and Moshe Y. Vardi. 2nd International Workshop on Strategic Reasoning, Apr 2014, 2014-04-06, France. EPTCS, 146, pp.11, 2014, EPTCS. 〈10.4204/EPTCS.146.13〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01098740
Contributeur : Sophie Pinchinat <>
Soumis le : lundi 7 septembre 2015 - 10:46:48
Dernière modification le : mercredi 11 avril 2018 - 02:00:30
Document(s) archivé(s) le : mardi 8 décembre 2015 - 11:40:06

Fichier

SR2014.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Citation

Guillaume Aucher, Bastien Maubert, Sophie Pinchinat. Automata Techniques for Epistemic Protocol Synthesis. Fabio Mogavero and Aniello Murano and Moshe Y. Vardi. 2nd International Workshop on Strategic Reasoning, Apr 2014, 2014-04-06, France. EPTCS, 146, pp.11, 2014, EPTCS. 〈10.4204/EPTCS.146.13〉. 〈hal-01098740〉

Partager

Métriques

Consultations de la notice

287

Téléchargements de fichiers

57