We introduce measures of uncertainty that are based on Depth-Bounded Logics and resemble belief functions. We show that our measures can be seen as approximation of classical probability measures over classical logic, and that a variant of the PSAT problem for them is solvable in polynomial time.

Baldi P., D’Agostino M., Hosni H. (2020) “Depth-Bounded Approximations of Probability”. In: Lesot MJ. et al. (eds) Information Processing and Management of Uncertainty in Knowledge-Based Systems. IPMU 2020. Communications in Computer and Information Science, vol 1239. Springer, Cham DOI: 10.1007/978-3-030-50153-2_45