Parameterized complexity results for a model of theory of mind based on dynamic epistemic logic
Number of pages
SourceElectronic Proceedings in Theoretical Computer Science, 215, (2016), pp. 246-263
Article / Letter to editor
Display more detailsDisplay less details
SW OZ DCC AI
Electronic Proceedings in Theoretical Computer Science
SubjectCognitive artificial intelligence; DI-BCB_DCC_Theme 2: Perception, Action and Control
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.
Upload full text
Use your RU credentials (u/z-number and password) to log in with SURFconext to upload a file for processing by the repository team.