Epistemic Reasoning in Logic Programs
Yan Zhang · 2014
Although epistemic logic programming has an en-hanced capacity to handle complex incomplete in-formation reasoning and represent agents ' epis-temic behaviours, it embeds a signicantly higher computational complexity than non-disjunctive and disjunctive answer set programming. In this paper, we investigate some important properties of epis-temic logic programs. In particular, we show that Lee and Lifschitz's result on loop formulas for dis-junctive logic programs can be extended to a spe-cial class of epistemic logic programs. We also study the polysize model property for epistemic logic programs. Based on these discoveries, we identify two non-trivial classes of epistemic logic programs whose consistency checking complexity is reduced from PSPACE-complete to NP-complete and P2-complete respectively. We observe that many important applications on epistemic repre-sentation fall into these two classes of epistemic logic programs. 1