Knowledge Compilation in Multi-Agent Epistemic Logics
  Epistemic logics are a primary formalism for multi-agent systems but major
reasoning tasks in such epistemic logics are intractable, which impedes
applications of multi-agent epistemic logics in automatic planning. Knowledge
compilation provides a promising way of resolving the intractability by
identifying expressive fragments of epistemic logics that are tractable for
important reasoning tasks such as satisfiability and forgetting. The property
of logical separability allows to decompose a formula into some of its
subformulas and thus modular algorithms for various reasoning tasks can be
developed. In this paper, by employing logical separability, we propose an
approach to knowledge compilation for the logic Kn by defining a normal form
SDNF. Among several novel results, we show that every epistemic formula can be
equivalently compiled into a formula in SDNF, major reasoning tasks in SDNF are
tractable, and formulas in SDNF enjoy the logical separability. Our results
shed some lights on modular approaches to knowledge compilation. Furthermore,
we apply our results in the multi-agent epistemic planning. Finally, we extend
the above result to the logic K45n that is Kn extended by introspection axioms
4 and 5.
