Nonmonotonic reasoning from conditional knowledge bases with system W (Q2075375)

This is an article in the context of defeasible reasoning. Intuitively, knowledge bases comprise conditional axioms to express that truth of an expression ``usually'' implies truth of another expression, leaving anyhow the possibility for the second expression to not hold. A preference over the possible interpretations, or worlds, for such knowledge bases is usually employed to define a meaningful form of reasoning, as intuitively is expected that worlds satisfying more conditional axioms are more plausible than others. The specific preference relation that is adopted actually characterizes the resulting reasoning system, as for example one may opt for several different types of quantitative or qualitative preference relations. The first part of this article focuses on ranking functions, which essentially assign a natural number, called rank, to each model of the knowledge base's input, so that models with the lowest rank are preferred over the others. In such a context, an interesting question to gain insight into the complexity of the problem, and therefore to understand what can be a reasonable solving strategy, is \textit{what can be an upper bound on the rank to consider?} An interesting result in this direction is shown in Section 7, where the authors present a construction obtaining a knowledge base for which a ranking function presented in the literature needs rank values exponential with respect to the number of conditional axioms in the input knowledge base. I found such a result interesting in the light that the upper bound was actually conjectured to be linear, and some experimental assessment was confirming the conjecture. In the second part of the article, the authors come up with a different semantics for knowledge bases comprising conditional axioms, which is named \textit{system W} and is not based on ranking functions. Actually, the authors formally prove that the inference system W cannot be characterized by any ranking function. At the same level of formality, the authors show that system W has several good properties, among them the generally accepted postulates of system P, the ``industry standard'' for qualitative nonmonotonic inference relations.