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

June 24, 2016 · The Ethereal · 🏛 Theoretical Aspects of Rationality and Knowledge

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Iris van de Pol, Iris van Rooij, Jakub Szymanik arXiv ID 1606.07526 Category cs.LO: Logic in CS Cross-listed cs.AI Citations 8 Venue Theoretical Aspects of Rationality and Knowledge Last Checked 5 months ago
Abstract
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.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 🎉 Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

📜 Similar Papers

In the same crypt — Logic in CS