The complexity of approximations for epistemic synthesis (extended abstract)

Xiaowei Huang
(UNSW Australia )
Ron van der Meyden
(UNSW Australia )

Epistemic protocol specifications allow programs, for settings in which multiple agents act with incomplete information, to be described in terms of how actions are related to what the agents know. They are a variant of the knowledge-based programs of Fagin et al [Distributed Computing, 1997], motivated by the complexity of synthesizing implementations in that framework. The paper proposes an approach to the synthesis of implementations of epistemic protocol specifications, that reduces the problem of finding an implementation to a sequence of model checking problems in approximations of the ultimate system being synthesized. A number of ways to construct such approximations is considered, and these are studied for the complexity of the associated model checking problems. The outcome of the study is the identification of the best approximations with the property of being PTIME implementable.

In Pavol Černý, Viktor Kuncak and Madhusudan Parthasarathy: Proceedings Fourth Workshop on Synthesis (SYNT 2015), San Francisco, CA, USA, 18th July 2015, Electronic Proceedings in Theoretical Computer Science 202, pp. 120–137.
Published: 2nd February 2016.

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