Belief Update for Proper Epistemic Knowledge Bases

Abstract

Reasoning about the nested beliefs of others is important in many multi-agent scenarios. While epistemic and doxastic logics lay a solid groundwork to approach such reasoning, the computational complexity of these logics is often too high for many tasks. Proper Epistemic Knowledge Bases (PEKBs) enforce two syntactic restrictions on formulae to obtain efficient querying: both disjunction and infinitely long nestings of modal operators are not permitted. PEKBs can be compiled, in exponential time, to a prime implicate formula that can be queried in polynomial time, while more recently, it was shown that consistent PEKBs had certain logical properties that meant this compilation was unnecessary..