Analysis of the syntactic computation of Fagin-Halpern conditioning in possibilistic logic
Omar Et-targuy, Salem Benferhat, Carole Delenne, Ahlame Begdouri · International Journal of Approximate Reasoning · 2025
Conditioning is an essential operation in knowledge representation and uncertainty modeling. It enables a priori beliefs to be adjusted in response to new information considered to be fully certain. This work focuses on the computation of Fagin and Halpern (FH-)conditioning in the context where uncertain information is represented by weighted or possibilistic logic belief bases. Weighted belief bases are extensions of classical logic belief bases where a weight or degree of belief is associated with each propositional logic formula. This paper proposes a characterization of the syntactic computation of the revision of weighted belief bases in the light of new information, which is in full agreement with the semantics of the FH-conditioning of possibility distributions. We show that the size of the revised belief base is linear with respect to the size of the initial base and that the computational complexity amounts to performing O ( log 2 ( n ) ) calls to the propositional logic satisfiability tests, where n is the number of different degrees of certainty used in the initial belief base. The last section of this paper examines both semantically and syntactically FH-conditioning under uncertain information, within the framework of possibility theory. • Reviews possibilistic logic and the use of weighted belief bases to represent uncertainty. • Introduces FH-conditioning within the framework of possibility theory. • Proposes a syntactic computation of FH-conditioning using three transformation steps. • Extends FH-conditioning to the case of uncertain observations. • Discusses complexity and interpretation of FH-conditioning as belief revision or update.