Reasoning About Typicality in Low Complexity DLs: The Logics εL~⊥T_(min) and DL-Lite_c T_(min)

摘要

We propose a nonmonotonic extension of low complexity Description LogicsεL~⊥ and DL-Lite_(core) for reasoning about typicality and defeasible properties. The resulting logics are calledεL~⊥T_(min) and DL-Lite_cT_(min). Concerning DL-Lite_cT_(min), we prove that entailment is in (Π_2)~p. With regard to εL~⊥T_(min), we first show that entailment remains EXPTIME-hard. Next we consider the known fragment of Left LocalεL~⊥T_(min), and we prove that the complexity of entailment drops to (Π_2)~p.