×

zbMATH — the first resource for mathematics

Algorithms for possibility assessments: coherence and extension. (English) Zbl 1214.68394
Summary: In this paper we study the computational aspects of coherence and extension of partial possibility assessments, both in an unconditional and a conditional setting, providing complexity results and algorithms for each problem. In particular, we propose an algorithm to check the coherence of a partial unconditional assessment which is based on propositional satisfiability. For the conditional case, we firstly prove a new characterization of coherent conditional assessments that allows us to define an algorithm again based on propositional satisfiability. The extension problem, in both settings, is solved by means of a search algorithm which relies on the corresponding coherence procedure.

MSC:
68T37 Reasoning under uncertainty in the context of artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ben Amor, N.; Benferhat, S., Graphoid properties of qualitative possibilistic independence relations, International journal of uncertainty, fuzziness and knowledge-based systems, 13, 1, 59-96, (2005) · Zbl 1096.68147
[2] Ben Amor, N.; Benferhat, S.; Dubois, D.; Mellouli, K.; Prade, H., A theoretical framework for possibilistic independence in weakly ordered setting, International journal of uncertainty, fuzziness and knowledge-based systems, 10, 2, 117-155, (2002) · Zbl 1084.68126
[3] Ben Amor, N.; Benferhat, S.; Mellouli, K., Anytime propagation algorithm for MIN-based possibilistic graphs, Soft computing, 8, 150-161, (2005)
[4] Baioletti, M.; Capotorti, A.; Tulipani, S.; Vantaggi, B., Elimination of Boolean variables for probabilistic coherence, Soft computing, 4, 2, 81-88, (2000)
[5] M. Baioletti, G. Coletti, D. Petturiti, B. Vantaggi, Coherent conditional possibilities in medical diagnosis, in: J. Vejnarová, T. Kroupa (Eds.), Proceedings of the 8th Workshop on Uncertainty Processing, Liblice, Czech Republic, 2009, pp. 13-22.
[6] Baroni, P.; Vicig, P., An uncertainty interchange format with imprecise probabilities, International journal of approximate reasoning, 40, 3, 147-180, (2005) · Zbl 1110.68145
[7] Benferhat, S.; Dubois, D.; Garcia, L.; Prade, H., On the transformation between possibilistic logic bases and possibilistic causal networks, International journal of approximate reasoning, 29, 2, 135-173, (2002) · Zbl 1015.68204
[8] Benferhat, S.; Dubois, D.; Prade, H.; Williams, M.A., A framework for iterated belief revision using possibilistic counterparts to Jeffrey’s rule, Fundamenta informaticae, 99, 147-168, (2010) · Zbl 1205.68391
[9] Biacino, L.; Gerla, G., Generated necessities and possibilities, International journal of intelligent systems, 7, 5, 445-454, (1992) · Zbl 0761.68090
[10] Biazzo, V.; Gilio, A.; Lukasiewicz, T.; Sanfilippo, G., Probabilistic logic under coherence: complexity and algorithms, Annals of mathematics and artificial intelligence, 45, 1-2, 35-81, (2005) · Zbl 1083.03027
[11] C. Borgelt, J. Gebhardt, R. Kruse, in: G. Della Riccia, H.J. Lenz (Eds.), Possibilistic Graphical Models, Computational Intelligence in Data Mining, Springer, 2000, pp. 51-68. · Zbl 0979.68106
[12] Bouchon-Meunier, B.; Coletti, G.; Marsala, C., Conditional possibility and necessity, (), 59-71 · Zbl 1015.68191
[13] Bouchon-Meunier, B.; Coletti, G.; Marsala, C., Independence and possibilistic conditioning, Annals of mathematics and artificial intelligence, 35, 107-123, (2002) · Zbl 1004.60001
[14] Capotorti, A.; Vantaggi, B., Locally strong coherence in inference processes, Annals of mathematics and artificial intelligence, 35, 1-4, 125-149, (2002) · Zbl 1014.68146
[15] Coletti, G.; Scozzafava, R., Conditioning and inference in intelligent systems, Soft computing, 3, 118-130, (1999)
[16] Coletti, G.; Scozzafava, R., From conditional events to conditional measures: a new axiomatic approach, Annals of mathematics and artificial intelligence, 32, 373-392, (2001) · Zbl 1314.68306
[17] Coletti, G.; Scozzafava, R., Probabilistic logic in a coherent setting, () · Zbl 1005.60007
[18] Coletti, G.; Vantaggi, B., Possibility theory: conditional independence, Fuzzy sets and systems, 157, 1491-1513, (2006) · Zbl 1092.68094
[19] Coletti, G.; Vantaggi, B., T-conditional possibilities: coherence and inference, Fuzzy sets and systems, 160, 306-324, (2009) · Zbl 1178.60006
[20] da Costa Pereira, C.; Garcia, F.; Lang, J.; Martin-Clouaire, R., Possibilistic planning: representation and complexity, (), 143-155
[21] De Baets, B.; de Cooman, G.; Kerre, E., The construction of possibility measures from samples on T-semi-partitions, Information sciences, 106, 3-24, (1998) · Zbl 1031.94555
[22] De Baets, B.; Tsiporkova, E.; Mesiar, R., Conditioning in possibility theory with strict order norms, Fuzzy sets and systems, 106, 2, 221-229, (1999) · Zbl 0985.28015
[23] de Cooman, G., Possibility theory I: the measure- and integral-theoretic groundwork, International journal of general systems, 25, 291-323, (1997) · Zbl 0955.28012
[24] de Cooman, G., Possibility theory II: conditional possibility, International journal of general systems, 25, 325-351, (1997) · Zbl 0955.28013
[25] de Finetti, B., Sull’impostazione assiomatica del calcolo delle probabilità, Annali università di trieste, 19, 3-55, (1949), (Eng. trans. in Ch. 5 of Probability, Induction, Statistics — Wiley, London) · Zbl 0036.20703
[26] Destercke, S.; Dubois, D.; Chojnacki, E., Possibilistic information fusion using maximal coherent subsets, IEEE transactions on fuzzy systems, 17, 1, 79-92, (2009)
[27] Dubois, D.; Lang, J.; Prade, H., Automated reasoning using possibilistic logic: semantics, belief revision, and variable certainty weights, IEEE transactions on knowledge and data engineering, 6, 1, 64-71, (1994)
[28] Dubois, D.; Lang, J.; Prade, H., Possibilistic logic, (), 439-513
[29] Dubois, D.; Prade, H., Possibility theory, (1988), Plenum Press New York · Zbl 0645.68108
[30] Dubois, D.; Prade, H., The logical view of conditioning and its application to possibility and evidence theories, International journal of approximate reasoning, 4, 1, 23-46, (1990) · Zbl 0696.03006
[31] Dubois, D.; Prade, H., Possibilistic logic, preferential models, non-monotonicity and related issues, (), 419-424 · Zbl 0744.68116
[32] Dubois, D.; Prade, H., A synthetic view of belief revision with uncertain inputs in the framework of possibility theory, International journal of approximate reasoning, 17, 295-324, (1997) · Zbl 0935.03026
[33] Dubois, D.; Prade, H., Possibility theory and its applications: a retrospective and prospective view, (), 5-11
[34] Dubois, D.; Prade, H., Possibilistic logic: a retrospective and prospective view, Fuzzy sets and systems, 144, 1, 3-23, (2004) · Zbl 1076.68084
[35] Ferracuti, L.; Vantaggi, B., Independence and conditional possibility for strictly monotone triangular norms, International journal of intelligent systems, 21, 299-323, (2006) · Zbl 1088.60003
[36] Georgakopoulos, G.F.; Kavvadias, D.J.; Papadimitriou, C.H., Probabilistic satisfiability, Journal of complexity, 4, 1, 1-11, (1988) · Zbl 0647.68049
[37] Hisdal, E., Conditional possibilities independence and noninteraction, Fuzzy sets and systems, 1, 4, 283-297, (1978) · Zbl 0393.94050
[38] Prade, H.; Testemale, C., Generalizing database relational algebra for the treatment of incomplete/uncertain information and vague queries, Information sciences, 34, 2, 115-143, (1984) · Zbl 0552.68082
[39] Sandri, S.A.; Dubois, D.; Kalfsbeek, H.W., Elicitation, assessment, and pooling of expert judgments using possibility theory, IEEE transactions on fuzzy systems, 3, 4, 313-335, (1995) · Zbl 0884.68118
[40] Schiex, T., Possibilistic constraint satisfaction problems or “how to handle soft constraints?”, (), 268-275
[41] Vejnarová, J., Conditional independence relations in possibility theory, International journal of uncertainty, fuzziness and knowledge-based systems, 8, 2, 253-269, (2000) · Zbl 1113.68536
[42] Z. Wang, Extension of possibility measures defined on an arbitrary nonempty class of sets, in: Proceedings of the International Fuzzy System Association World Congress (IFSA ’85), Palma de Mallorca, 1985.
[43] Williams, M.A., On the logic of theory base change, (), 86-105 · Zbl 0988.03512
[44] Williams, M.A., Iterated theory base change: a computational model, (), 1541-1547
[45] Zadeh, L.A., Fuzzy sets as a basis for a theory of possibility, Fuzzy sets and systems, 1, 1, 3-28, (1978) · Zbl 0377.04002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.