Optimizing the computation of overriding in DLN

One of the factors that is hindering the adoption of nonmonotonic description logics in applications is performance. Even when monotonic and nonmonotonic inferences have the same asymptotic complexity, the implementation of nonmonotonic reasoning may be significantly slower. This happens also with the family of nonmonotonic logics DLN. In this work we address this issue by introducing two optimizations for reasoning in DLN. The first optimization, called optimistic evaluation, aims at exploiting incremental reasoning in a better way. The second is a module extractor for DLN, that has the purpose of focusing reasoning on a relevant subset of the knowledge base. The proposed optimization iterates the module extractor that, unlike classical module extractors, is not idempotent, in general. We prove that the proposed optimizations are correct and complete, and assess them through extensive experiments. Our results prove that optimized DLN reasoning is often compatible with interactive query answering, which brings nonmonotonic description logics closer to practical applications.