Lexicographic Entailment, Syntax Splitting and the Drowning Problem

Lexicographic Entailment, Syntax Splitting and the Drowning Problem

Jesse Heyninck, Gabriele Kern-Isberner, Thomas Meyer

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 2662-2668. https://doi.org/10.24963/ijcai.2022/369

Lexicographic inference is a well-known and popular approach to reasoning with non-monotonic conditionals. It is a logic of very high-quality, as it extends rational closure and avoids the so-called drowning problem. It seems, however, this high quality comes at a cost, as reasoning on the basis of lexicographic inference is of high computational complexity. In this paper, we show that lexicographic inference satisfies syntax splitting, which means that we can restrict our attention to parts of the belief base that share atoms with a given query, thus seriously restricting the computational costs for many concrete queries. Furthermore, we make some observations on the relationship between c-representations and lexicographic inference, and reflect on the relation between syntax splitting and the drowning problem.
Keywords:
Knowledge Representation and Reasoning: Non-monotonic Reasoning