Parameterized Complexity Results for a Model of Theory of Mind Based on Dynamic Epistemic Logic

Iris van de Pol
(University of Amsterdam, ILLC)
Iris van Rooij
(Radboud University Nijmegen, Donders Institute for Brain, Cognition and Behaviour)
Jakub Szymanik
(University of Amsterdam, ILLC)

In this paper we introduce a computational-level model of theory of mind (ToM) based on dynamic epistemic logic (DEL), and we analyze its computational complexity. The model is a special case of DEL model checking. We provide a parameterized complexity analysis, considering several aspects of DEL (e.g., number of agents, size of preconditions, etc.) as parameters. We show that model checking for DEL is PSPACE-hard, also when restricted to single-pointed models and S5 relations, thereby solving an open problem in the literature. Our approach is aimed at formalizing current intractability claims in the cognitive science literature regarding computational models of ToM.

In R Ramanujam: Proceedings Fifteenth Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2015), Carnegie Mellon University, Pittsburgh, USA, June 4-6, 2015, Electronic Proceedings in Theoretical Computer Science 215, pp. 246–263.
Published: 23rd June 2016.

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