Exploring the tractability border in epistemic tasks

DOI10.1007/s11229-012-0215-7zbMath1310.03022OpenAlexW1978670170MaRDI QIDQ484931

Jakub Szymanik, Lena Kurzen, Cédric Dégremont

Publication date: 8 January 2015

Published in: Synthese (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11229-012-0215-7

zbMATH Keywords

computational complexitymulti-agent systemsepistemic logicepistemic reasoning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27) Logics of knowledge and belief (including belief change) (03B42) Agent technology and artificial intelligence (68T42)

Related Items

Unnamed Item, Parameterized complexity of theory of mind reasoning in dynamic epistemic logic, Dynamics of lying, Logic and Complexity in Cognitive Science

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Logic and social cognition. The facts matter, and so do computational models
• An internal version of epistemic logic
• Group announcement logic
• The complexity of reasoning about knowledge and time. I: Lower bounds
• Group-theoretic algorithms and graph isomorphism
• A guide to completeness and complexity for modal logics of knowledge and belief
• Deciding bisimilarity is P-complete
• Generalized quantifiers and modal logic
• Interactive epistemology. I: Knowledge
• Logics for epistemic programs
• Knowledge updates: Semantics and complexity issues
• The Logic of Public Announcements, Common Knowledge, and Private Suspicions
• Logical Dynamics of Information and Interaction
• Invariance Properties of Quantifiers and Multiagent Information Exchange
• ‘KNOWABLE’ AS ‘KNOWN AFTER AN ANNOUNCEMENT’
• Dynamic Epistemic Logic and Knowledge Puzzles
• Simulation and Information: Quantifying over Epistemic Events
• Reinforcement-based vs. Belief-based Learning Models in Experimental Asymmetric-information Games
• Reducibility among Combinatorial Problems
• Paths, Trees, and Flowers
• LOGICS FOR THE RELATIONAL SYLLOGISTIC