×

Reasoning with prioritized information by iterative aggregation of distance functions. (English) Zbl 1158.68499

Summary: We introduce a general framework for reasoning with prioritized propositional data by aggregation of distance functions. Our formalism is based on a possible world semantics, where conclusions are drawn according to the most ‘plausible’ worlds (interpretations), namely: the worlds that are as ‘close’ as possible to the set of premises, and, at the same time, are as ‘faithful’ as possible to the more reliable (or important) information in this set. This implies that the consequence relations that are induced by our framework are derived from a pre-defined metric on the space of interpretations, and inferences are determined by a ranking function applied to the premises. We study the basic properties of the entailment relations that are obtained by this framework, and relate our approach to other methods of maintaining incomplete and inconsistent information, most specifically in the contexts of (iterated) belief revision, consistent query answering in database systems, and integration of prioritized data sources.

MSC:

68T30 Knowledge representation
68T37 Reasoning under uncertainty in the context of artificial intelligence
68U35 Computing methodologies for information systems (hypertext navigation, interfaces, decision support, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alchourrón, C. E.; Gärdenfors, P.; Makinson, D., On the logic of theory change: Partial meet contraction and revision function, Journal of Symbolic Logic, 50, 510-530 (1985) · Zbl 0578.03011
[2] Arenas, M.; Bertossi, L.; Chomicki, J., Answer sets for consistent query answering in inconsistent databases, Theory and Practice of Logic Programming, 3, 4-5, 393-424 (2003) · Zbl 1079.68026
[3] Arieli, O., Four-valued logics for reasoning with uncertainty in prioritized data, (Bouchon-Meunier, B.; Yager, R.; Zadeh, L., Information, Uncertainty, Fusion (1999), Kluwer), 293-304
[4] O. Arieli, Distance-based paraconsistent logics, International Journal of Approximate Reasoning (2008), doi: 10.1016/j.ijar.2007.07.002; O. Arieli, Distance-based paraconsistent logics, International Journal of Approximate Reasoning (2008), doi: 10.1016/j.ijar.2007.07.002 · Zbl 1189.03035
[5] Arieli, O., Reasoning with prioritized data by aggregation of distance functions, (Proc. AGI’08. Proc. AGI’08, Frontiers in Artificial Intelligence and Applications, vol. 171 (2008), IOS Press), 27-38
[6] Arieli, O.; Avron, A., General patterns for nonmonotonic reasoning: From basic entailments to plausible relations, The Logic Journal of the Interest Group in Pure and Applied Logics, 8, 2, 119-148 (2000) · Zbl 0966.03024
[7] Arieli, O.; Denecker, M.; Bruynooghe, M., Distance semantics for database repair, Annals of Mathematics and Artificial Intelligence, 50, 3-4, 389-415 (2007) · Zbl 1126.68034
[8] Arieli, O.; Denecker, M.; Van Nuffelen, B.; Bruynooghe, M., Coherent integration of databases by abductive logic programming, Artificial Intelligence Research, 21, 245-286 (2004) · Zbl 1080.68570
[9] Arieli, O.; Zamansky, A., Some simplified forms of reasoning with distance-based entailments, (Proc. 21st Canadian Conference on Artificial Intelligence. Proc. 21st Canadian Conference on Artificial Intelligence, LNAI, vol. 5032 (2008), Springer), 36-47
[10] Batens, D., Dynamic dialectical logics, (Priest, G.; Routely, R.; Norman, J., Paraconsistent Logic. Essay on the Inconsistent (1989), Philosophia Verlag), 187-217 · Zbl 0695.03011
[11] Batens, D., Inconsistency-adaptive logics, (Orlowska, E., Logic at Work (1998), Physica Verlag), 445-472 · Zbl 0923.03036
[12] S. Benferhat, C. Cayrol, D. Dubois, J. Lang, H. Prade, Inconsistency management and prioritized syntax-based entailment, in: Proc. IJCAI’93, 1993, pp. 640-645; S. Benferhat, C. Cayrol, D. Dubois, J. Lang, H. Prade, Inconsistency management and prioritized syntax-based entailment, in: Proc. IJCAI’93, 1993, pp. 640-645
[13] S. Benferhat, D. Dubois, H. Prade, How to infer from inconsistent beliefs without revising? in: Proc. IJCAI’95, 1995, pp. 1449-1455; S. Benferhat, D. Dubois, H. Prade, How to infer from inconsistent beliefs without revising? in: Proc. IJCAI’95, 1995, pp. 1449-1455
[14] Benferhat, S.; Kaci, S., Logical representation and fusion of prioritized information based on guaranteed possibility measures: Application to the distance-based merging of classical bases, Artificial Intelligence, 148, 291-333 (2003) · Zbl 1082.68833
[15] Bertossi, L., Consistent query answering in databases, SIGMOD Records, 35, 2, 68-76 (2006)
[16] G. Brewka, Preferred sub-theories: An extended logical framework for default reasoning, in: Proc. IJCAI’89, 1989, pp. 1043-1048; G. Brewka, Preferred sub-theories: An extended logical framework for default reasoning, in: Proc. IJCAI’89, 1989, pp. 1043-1048 · Zbl 0713.68053
[17] Calì, A.; Calvanese, D.; De Giacomo, G.; Lanzerini, M., Data integration under integrity constraints, Information Systems, 29, 2, 147-163 (2004)
[18] Dalal, M., Investigations into a theory of knowledge base revision, (Proc. AAAI’88 (1988), AAAI Press), 475-479
[19] Darwiche, A.; Pearl, J., On the logic of iterated belief revision, Artificial Intelligence, 89, 1-29 (1997) · Zbl 1018.03012
[20] J. Delgrande, D. Dubois, J. Lang, Iterated revision and prioritized merging, in: Proc. KR’06, 2006, pp. 210-220; J. Delgrande, D. Dubois, J. Lang, Iterated revision and prioritized merging, in: Proc. KR’06, 2006, pp. 210-220
[21] D. Dubois, J. Lang, H. Prade, Possibilistic logic, in: D. Gabbay, C. Hogger, J. Robinson, (Eds.), Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 3, 1994, pp. 439-513; D. Dubois, J. Lang, H. Prade, Possibilistic logic, in: D. Gabbay, C. Hogger, J. Robinson, (Eds.), Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 3, 1994, pp. 439-513
[22] Gabbay, D., Theoretical foundation for non-monotonic reasoning, Part II: Structured non-monotonic theories, (Proc. SCAI’91 (1991), IOS Press), 475-479
[23] Gauwin, O.; Konieczny, S.; Marquis, P., Conciliation through iterated belief merging, Journal of Logic and Computation, 17, 5, 909-937 (2007) · Zbl 1135.68049
[24] Goldszmidt, M.; Pearl, J., Qualitative probabilities for default reasoning, belief revision, and causal modeling, Artificial Intelligence, 84, 57-112 (1996) · Zbl 1497.68457
[25] Jin, Y.; Thielscher, M., Iterated revision, revised, Artificial Intelligence, 171, 1-18 (2007) · Zbl 1168.03318
[26] Katsuno, H.; Mendelzon, A. O., Propositional knowledge base revision and minimal change, Artificial Intelligence, 52, 263-294 (1991) · Zbl 0792.68182
[27] S. Konieczny, J. Lang, P. Marquis, Distance-based merging: A general framework and some complexity results, in: Proc. KR’02, 2002, pp. 97-108; S. Konieczny, J. Lang, P. Marquis, Distance-based merging: A general framework and some complexity results, in: Proc. KR’02, 2002, pp. 97-108
[28] Konieczny, S.; Pino Pérez, R., Merging information under constraints: A logical framework, Logic and Computation, 12, 5, 773-808 (2002) · Zbl 1020.68086
[29] Kraus, S.; Lehmann, D.; Magidor, M., Nonmonotonic reasoning, preferential models and cumulative logics, Artificial Intelligence, 44, 1-2, 167-207 (1990) · Zbl 0782.03012
[30] Lafage, C.; Lang, J., Propositional distances and preference representation, (Proc. ECSQARU’01. Proc. ECSQARU’01, LNAI, vol. 2143 (2001), Springer), 48-59 · Zbl 1005.68547
[31] Lehmann, D., Another perspective on default reasoning, Annals of Mathematics and Artificial Intelligence, 15, 1, 61-82 (1995) · Zbl 0857.68096
[32] Lehmann, D.; Magidor, M., What does a conditional knowledge base entail?, Artificial Intelligence, 55, 1-60 (1992) · Zbl 0762.68057
[33] Lopatenko, A.; Bertossi, L., Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics, (Proc. ICDT’07. Proc. ICDT’07, LNCS, vol. 4353 (2007), Springer), 179-193
[34] D. Makinson, General patterns in nonmonotonic reasoning, in: D. Gabbay, C. Hogger, J. Robinson, (Eds.), Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 3, 1994, pp. 35-110; D. Makinson, General patterns in nonmonotonic reasoning, in: D. Gabbay, C. Hogger, J. Robinson, (Eds.), Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 3, 1994, pp. 35-110
[35] B. Nebel, Belief revision and default reasoning: Syntax-based approaches, in: Proc. KR’01, 1991, pp. 417-428; B. Nebel, Belief revision and default reasoning: Syntax-based approaches, in: Proc. KR’01, 1991, pp. 417-428 · Zbl 0765.68198
[36] B. Nebel, Base revision operations and schemes: Semantics, representation, and complexity, in: Proc. ECAI’94, 1994, pp. 341-345; B. Nebel, Base revision operations and schemes: Semantics, representation, and complexity, in: Proc. ECAI’94, 1994, pp. 341-345
[37] Reiter, R., On closed world databases, (Logic and Databases (1978), Plenum Press), 55-76
[38] Subrahmanian, V. S., Mechanical proof procedures for many valued lattice-based logic programming, Journal of Non-Classical Logic, 7, 7-41 (1990) · Zbl 0724.03012
[39] Tarski, A., Introduction to Logic (1941), Oxford University Press · JFM 67.0033.03
[40] M. Williams, Iterated theory base change: A computational model, in: Proc. IJCAI’95, 1995, pp. 1541-1547; M. Williams, Iterated theory base change: A computational model, in: Proc. IJCAI’95, 1995, pp. 1541-1547
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.