Possibilistic logic offers a unified framework for revising prioritized pieces of information and for reasoning with conditional knowledge bases. A conditional assertion of the form "generally, if α is true then β is true" is interpreted as a constraint expressing that the possibility degree of having α ∧ β being true is greater than the possibility degree of having α ∧ ┐β being true. Recently, an important extension of possibilistic logic has been proposed to deal with partially pre-ordered bases in order to avoid comparing unrelated pieces of information. This paper establishes relationships between reasoning from partially pre-ordered bases and reasoning from conditional knowledge bases. It contains two important contributions. The first contribution consists in identifying conditions under which a partially ordered belief base can be encoded as a set of conditional assertions, and conversely. In particular, we provide the correspondences between the concept of compatible possibility distributions used for conditional assertions and the one of compatible prioritized bases used for partially pre-ordered bases. The second important contribution of this paper consists in providing the computational complexity of reasoning with partially pre-ordered bases using the well-known possibilistic and inclusion-based policies.
展开▼
