Tractable Deduction in Some Fragments of Auto-Epistemic Logic

摘要

It is well-known that deduction in non-monotonic logic is not at all easy. Inthis document we consider the three fragments of default logic that have been shown to have tractable decision problems, and we show that the corresponding decision problems for auto-epistemic logic have similar complexities. This all serves to demonstrate that stratified theories (for which, due to its allowing only one extension, all decision problems collapse in to one) form not the only reasonable tractable fragment of auto-epistemic logic.