×

Logic based merging. (English) Zbl 1233.03024

Summary: Belief merging aims at combining several pieces of information coming from different sources. In this paper we review the works on belief merging of propositional bases. We discuss the relationship between merging, revision, update and confluence, and some links between belief merging and social choice theory. Finally we mention the main generalizations of these works in other logical frameworks.

MSC:

03B42 Logics of knowledge and belief (including belief change)
91B14 Social choice
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alchourrón, C. E., Gärdenfors, P., & Makinson, D. (1985). On the logic of theory change: Partial meet contraction and revision functions. Journal of Symbolic Logic, 50, 510–530. · Zbl 0578.03011 · doi:10.2307/2274239
[2] Arieli, O. (2008). Distance-based paraconsistent logics. International Journal of Approximate Reasoning, 48(3), 766–783. · Zbl 1189.03035 · doi:10.1016/j.ijar.2007.07.002
[3] Arrow, K., Sen, A. K., & Suzumura, K. (Eds.) (2002). Handbook of Social Choice and Welfare, Vol. 1. North-Holland. · Zbl 1307.91009
[4] Arrow, K. J. (1963). Social choice and individual values (2nd ed.). New York: Wiley. · Zbl 0984.91513
[5] Ayoun, A., & Smets, P. (2001). Data association in multi-target detection using the transferable belief model. International Journal of Intelligent Systems, 16(10), 1167–1182. · Zbl 0988.68170 · doi:10.1002/int.1054
[6] Baral, C., Kraus, S., & Minker, J. (1991). Combining multiple knowledge bases. IEEE Transactions on Knowledge and Data Engineering, 3(2), 208–220. · Zbl 05108957 · doi:10.1109/69.88001
[7] Baral, C., Kraus, S., Minker, J., & Subrahmanian, V. S.(1992). Combining knowledge bases consisting of first-order theories. Computational Intelligence, 8(1), 45–71. · doi:10.1111/j.1467-8640.1992.tb00337.x
[8] Benferhat, S., Dubois, D., Kaci, S., & Prade, H. (2002). Possibilistic merging and distance-based fusion of propositional information. Annals of Mathematics and Artificial Intelligence, 34(1–3), 217–252. · Zbl 1001.68032 · doi:10.1023/A:1014446411602
[9] Benferhat, S., Dubois, D., Lang, J., Prade, H., Saffioti, A., & Smets, P. (1998). A general approach for inconsistency handling and merging information in prioritized knowledge bases. In Proceedings of the sixth international conference on principles of knowledge representation and reasoning (KR’98) (pp. 466–477).
[10] Benferhat, S., Dubois, D., & Prade, H. (1997). Some syntactic approaches to the handling of inconsistent knowledge bases: A comparative study, part 1: The flat case. Studia Logica, 58, 17–45. · Zbl 0867.68100 · doi:10.1023/A:1004987830832
[11] Benferhat, S., Dubois, D., & Prade, H. (1998). Logic at work (Ewa Orlowska, (eds)) (Vol. 24, Chapt. Some syntactic approaches to the handling of inconsistent knowledge bases: A comparative study.). Part 2: The prioritized case, pp. 473–511. Physica-Verlag, Heidelberg. · Zbl 0930.68149
[12] Benferhat, S., & Kaci, S. (2003). Fusion of possibilistic knowledge bases from a postulate point of view. International Journal of Approximate Reasoning, 33(3), 255–285. · Zbl 1059.68135 · doi:10.1016/S0888-613X(03)00018-5
[13] Benferhat, S., Lagrue, S., & Rossit, J. (2009). An analysis of sum-based incommensurable belief base merging. In Proceedings of the third international conference on scalable uncertainty management (SUM’08) (pp. 55–67). · Zbl 1433.03041
[14] Benferhat, S., Lagrue, S., & Rossit, J. (2009). Max-based prioritized information fusion without commensurability. Journal of Logic and Computation, 19(6), 1577–1610. · Zbl 1185.68701 · doi:10.1093/logcom/exp038
[15] Besnard, P., & Schaub, T. (1998). Signed systems for paraconsistent reasoning. Journal of Automated Reasoning, 20(1), 191–213. · Zbl 0893.68149 · doi:10.1023/A:1005957026440
[16] Bloch, I., Géraud, T., & Maître, H. (2003). Representation and fusion of heterogeneous fuzzy information in the 3D space for model-based structural recognition–application to 3D brain imaging. Artificial Intelligence, 148(1–2), 141–175. · Zbl 1082.68789 · doi:10.1016/S0004-3702(03)00018-3
[17] Bloch, I., Hunter, A., Appriou, A., Ayoun, A., Benferhat, S., Besnard, P., et al. (2001). Fusion: General concepts and characteristics. International Journal of Intelligent Systems, 16(10), 1107–1134. · Zbl 0989.68162 · doi:10.1002/int.1052
[18] Bloch, I., & Lang, J. (2000). Towards mathematical morpho-logics. In Proceedings of the eigth international conference on information processing and management of uncertainty in knowledge-based systems (IPMU’00) (pp. 1405–1412). · Zbl 1010.68185
[19] Booth, R. (2006). Social contraction and belief negotiation. Information Fusion, 7(1), 19–34. · Zbl 05422901 · doi:10.1016/j.inffus.2005.01.002
[20] Borgida, A. (1985). Language features for flexible handling of exceptions in information systems. ACM Transactions on Database Systems, 10, 563–603. · doi:10.1145/4879.4995
[21] Bovens, L., & Rabinowicz, W. (2006). Democratic answers to complex questions. An epistemic perspective. Synthese, 150, 131–153. · Zbl 1175.91060 · doi:10.1007/s11229-006-0005-1
[22] Brams, S. J., & Fishburn, P. C. (1983). Approval voting. Springer Verlag. · Zbl 0537.90001
[23] Chacón, J. L., & Pino Pérez, R. (2006). Merging operators: Beyond the finite case. Information Fusion, 7(1), 41–60. · Zbl 05422917 · doi:10.1016/j.inffus.2005.05.002
[24] Chopra, S., Ghose, A., & Meyer, T. (2006). Social choice theory, belief merging, and strategy-proofness. Information Fusion, 7(1), 61–79. · Zbl 05422923 · doi:10.1016/j.inffus.2005.05.003
[25] Condotta, J.-F., Kaci, S., Marquis, P., & Schwind, N. (2009). Merging qualitative constraint networks in a piecewise fashion. In Proceedings of the twenty first international conference on tools with artificial intelligence (ICTAI’09) (pp. 605–608).
[26] Condotta, J.-F., Kaci, S., Marquis, P., & Schwind, N. (2009). Merging qualitative constraints networks using propositional logic. In Proceedings of the tenth European conference on symbolic and quantitative approaches to reasoning with uncertainty (ECSQARU’09) (pp. 347–358). · Zbl 1245.68182
[27] Condotta, J.-F., Kaci, S., Marquis, P., & Schwind, N. (2010). Majority merging: From Boolean spaces to affine spaces. In Proceedings of the nineteenth European conference on artificial intelligence (ECAI’10) (pp. 627–632). · Zbl 1211.68422
[28] Coste-Marquis, S., Devred, C., Konieczny, S., Lagasquie-Schiex, M.-C., & Marquis, P. (2007). On the merging of Dung’s argumentation systems. Artificial Intelligence, 171, 740–753. · Zbl 1168.68563
[29] Dalal, M. (1988). Investigations into a theory of knowledge base revision: Preliminary report. In Proceedings of the AAAI conference on artificial intelligence (AAAI’88) (pp. 475–479).
[30] Darwiche, A., & Pearl, J. (1997). On the logic of iterated belief revision. Artificial Intelligence, 89, 1–29. · Zbl 1018.03012 · doi:10.1016/S0004-3702(96)00038-0
[31] Dastani, M., & van der Torre, L. W. N. (2002). Specifying the merging of desires into goals in the context of beliefs. In Proceedings of the EurAsia-ICT conference (LNCS 2510) (pp. 824–831). · Zbl 1025.68535
[32] Delgrande, J. P., Dubois, D., & Lang, J. (2006). Iterated revision as prioritized merging. In Proceedings of the tenth international conference on knowledge representation and reasoning (KR’06) (pp. 210–220).
[33] Delgrande, J. P., Liu, D. H., Schaub, T., & Thiele, S. (2007). COBA 2.0: A consistency-based belief change system. In Proceedings of the ninth international conference on symbolic and quantitative approaches to reasoning with uncertainty (ECSQARU’07) (pp. 78–90). · Zbl 1148.68492
[34] Delgrande, J. P., & Schaub, T. (2007). A consistency-based framework for merging knowledge bases. Journal of Applied Logic, 5(3), 459–477. · Zbl 1122.68120 · doi:10.1016/j.jal.2006.03.005
[35] Delgrande, J. P., Schaub, T., Tompits, H., & Woltran, S. (2009). Merging logic programs under answer set semantics. In Proceedings of the twenty fifth international conference on logic programming (ICLP’09) (pp. 160–174). · Zbl 1251.68057
[36] Dubois, D., Lang, J., & Prade, H. (1994). Possibilistic logic. In Handbook of logic in artificial intelligence and logic programming (Vol. 3). Oxford Science Publications. · Zbl 1009.03521
[37] Dung, P. M. (1995). On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial Intelligence, 77, 321–357. · Zbl 1013.68556 · doi:10.1016/0004-3702(94)00041-X
[38] Dupin de Saint-Cyr, F., & Lang, J. (2002). Belief extrapolation (or how to reason about observations and unpredicted change). In Proceedings of the eighth conference on principles of knowledge representation and reasoning (KR’02) (pp. 497–508). · Zbl 1216.68262
[39] Everaere, P., Konieczny, S., & Marquis, P. (2007). The strategy-proofness landscape of merging. Journal of Artificial Intelligence Research, 28, 49–105. · Zbl 1182.68049
[40] Everaere, P., Konieczny, S., & Marquis, P. (2008). Conflict-based merging operators. In Proceedings of the eleventh international conference on principles of knowledge representation and reasoning (KR’08) (pp. 348–357).
[41] Everaere, P., Konieczny, S., & Marquis, P. (2010). Disjunctive merging: Quota and gmin merging operators. Artificial Intelligence, 174(12–13), 824–849. · Zbl 1206.68288 · doi:10.1016/j.artint.2010.05.001
[42] Everaere, P., Konieczny, S., & Marquis, P. (2010). The epistemic view of belief merging: Can we track the truth?. In Proceedings of the nineteenth European conference on artificial intelligence (ECAI’10) (pp. 621–626). · Zbl 1211.68401
[43] Friedman, N., & Halpern, J. (1996). Belief revision: A critique. In Proceedings of the fifth international conference on principles of knowledge representation and reasoning (KR’96) (pp. 421–431). · Zbl 0949.03017
[44] Gärdenfors, P. (1988). Knowledge in flux. MIT Press. · Zbl 1229.03008
[45] Gärdenfors, P. (Ed.) (1992). Belief revision. Cambridge University Press. · Zbl 0801.68151
[46] Gauwin, O., Konieczny, S., & Marquis, P. (2007). Conciliation through iterated belief merging. Journal of Logic and Computation, 17(5), 909–937. · Zbl 1135.68049 · doi:10.1093/logcom/exm047
[47] Ghose, A., & Lin, Q. (2006). Viewpoints merging via incrementally elicited ranked structures. In Proceedings of the sixth international conference on quality software (QSIC ’06) (pp. 141–150).
[48] Gibbard, A. (1973). Manipulation of voting schemes. Econometrica, 41, 587–602. · Zbl 0325.90081 · doi:10.2307/1914083
[49] Gorogiannis, N., & Hunter, A. (2008). Implementing semantic merging operators using binary decision diagrams. International Journal of Approximate Reasoning, 49(1), 234–251. · Zbl 1184.68509 · doi:10.1016/j.ijar.2008.03.008
[50] Gorogiannis, N., & Hunter, A. (2008). Merging first-order knowledge using dilation operators. In Proceedings of the fifth international symposium on foundations of information and knowledge systems (FoIKS’08) (pp. 132–150). · Zbl 1138.68560
[51] Hansson, S. O. (1998). What’s new isn’t always best. Theoria, 1–13. (Special issue on non-prioritized belief revision).
[52] Herzig, A., & Rifi, O. (1998). Update operations: A review. In Proceedings of the thirteenth European conference on artificial intelligence (ECAI’98) (pp. 13–17).
[53] Hué, J., Papini, O., & Würbel, E. (2009). Merging belief bases represented by logic programs. In Proceedings of the tenth international conference on symbolic and quantitative approaches to reasoning with uncertainty (ECSQARU’09) (pp. 371–382). · Zbl 1245.68187
[54] Hunter, A. (2002). Logical fusion rules for merging structured news reports. Data & Knowledge Engineering, 42(1), 23–56. · Zbl 1053.68037 · doi:10.1016/S0169-023X(02)00026-5
[55] Hunter, A. (2002). Merging structured text using temporal knowledge. Data & Knowledge Engineering, 41(1), 29–66. · Zbl 1053.68038 · doi:10.1016/S0169-023X(02)00019-8
[56] Hunter, A., & Liu, W. (2006). Merging uncertain information with semantic heterogeneity in XML. Knowledge and Information Systems, 9(2), 230–258. · doi:10.1007/s10115-005-0220-y
[57] Hunter, A., & Liu, W. (2009). Knowledge base stratification and merging based on degree of support. In Proceedings of the tenth European conference on symbolic and quantitative approaches to reasoning with uncertainty (ECSQARU’09) (pp. 383–395). · Zbl 1245.68194
[58] Hunter, A., & Summerton, R. (2006). Merging news reports that describe events. Data & Knowledge Engineering, 59(1), 1–24. · doi:10.1016/j.datak.2005.06.005
[59] Kaci, S., Benferhat, S., Dubois, D., & Prade, H. (2000). A principled analysis of merging operations in possibilistic logic. In Proceedings of the sixteenth conference in uncertainty in artificial intelligence (UAI’00) (pp. 24–31).
[60] Katsuno, H., & Mendelzon, A. O. (1991). On the difference between updating a knowledge base and revising it. In Proceedings of the second international conference on principles of knowledge representation and reasoning (KR’91) (pp. 387–394). · Zbl 0765.68197
[61] Katsuno, H., & Mendelzon, A. O. (1991). Propositional knowledge base revision and minimal change. Artificial Intelligence, 52, 263–294. · Zbl 0792.68182 · doi:10.1016/0004-3702(91)90069-V
[62] Kelly, J. S. (1988). Social choice theory: An introduction. Springer-Verlag. · Zbl 0689.90002
[63] Konieczny, S. (2000). On the difference between merging knowledge bases and combining them. In Proceedings of the seventh international conference on principles of knowledge representation and reasoning (KR’00) (pp. 135–144).
[64] Konieczny, S. (2004). Belief base merging as a game. Journal of Applied Non-Classical Logics, 14(3), 275–294. · Zbl 1185.68693 · doi:10.3166/jancl.14.275-294
[65] Konieczny, S. (2009). Using transfinite ordinal conditional functions. In Proceedings of the tenth European conference on symbolic and quantitative approaches to reasoning with uncertainty (ECSQARU’09) (pp. 396–407). · Zbl 1245.68188
[66] Konieczny, S., Lang, J., & Marquis, P. (2004). DA2 merging operators. Artificial Intelligence, 157(1–2), 49–79. · Zbl 1085.68167 · doi:10.1016/j.artint.2004.04.008
[67] Konieczny, S., & Pino Pérez, R. (1998). On the logic of merging. In Proceedings of the sixth international conference on principles of knowledge representation and reasoning (KR’98) (pp. 488–498).
[68] Konieczny, S., & Pino Pérez, R. (2000). A framework for iterated revision. Journal of Applied Non-Classical Logics, 10(3–4), 339–367. · Zbl 1033.03506 · doi:10.1080/11663081.2000.10511003
[69] Konieczny, S., & Pino Pérez, R. (2002). Merging information under constraints: A logical framework. Journal of Logic and Computation, 12(5), 773–808. · Zbl 1020.68086 · doi:10.1093/logcom/12.5.773
[70] Konieczny, S., & Pino Pérez, R. (2002). On the frontier between arbitration and majority. In Proceedings of the eighth international conference on principles of knowledge representation and reasoning (KR’02) (pp. 109–118).
[71] Konieczny, S., & Pino Pérez, R. (2008). Confluence operators. In Proceedings of the eleventh European conference on logics in artificial intelligence (JELIA’08) (pp. 272–284). · Zbl 1178.68565
[72] Lang, J. (2007). Belief update revisited. In Proceedings of the twentieth international joint conference on artificial intelligence (IJCAI’07) (pp. 2517–2522).
[73] Lehmann, D. (1995). Belief revision, revised. In Proceedings of the fourteenth international joint conference on artificial intelligence (IJCAI’95) (pp. 1534–1540).
[74] Liberatore, P., & Schaerf, M. (1998). Arbitration (or how to merge knowledge bases). IEEE Transactions on Knowledge and Data Engineering, 10(1), 76–90. · Zbl 05108803 · doi:10.1109/69.667090
[75] Liberatore, P., & Schaerf, M. (2000). BReLS: A system for the integration of knowledge bases. In Proceedings of the seventh international conference on principles of knowledge representation and reasoning (KR’00) (pp. 145–152).
[76] Lin, J. (1996). Integration of weighted knowledge bases. Artificial Intelligence, 83(2), 363–378. · doi:10.1016/0004-3702(95)00019-4
[77] Lin, J., & Mendelzon, A. O. (1998). Merging databases under constraints. International Journal of Cooperative Information System, 7(1), 55–76. · doi:10.1142/S0218843098000040
[78] Lin, J., & Mendelzon, A. O. (1999). Knowledge base merging by majority. In Dynamic worlds: From the frame problem to knowledge management. · Zbl 0926.68135
[79] List, C., & Polak, B. (2010). Introduction to judgment aggregation. Journal of Economic Theory, 145(2), 441–466. · Zbl 1238.91061 · doi:10.1016/j.jet.2010.02.001
[80] Marquis de Condorcet. (1785). Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix. Paris.
[81] Meyer, T., Foo, N., Zhang, D., & Kwok, R. (2004). Logical foundations of negotiation: Outcome, concession and adaptation. In Proceedings of the AAAI conference on artificial intelligence (AAAI’04) (pp. 293–298).
[82] Meyer, T. A. (2001). On the semantics of combination operations. Journal of Applied Non-Classical Logics, 11(1–2), 59–84. · Zbl 1041.68095 · doi:10.3166/jancl.11.59-84
[83] Mu, K., Liu, W., Jin, Z., Lu, R., Yue, A., & Bell, D. A. (2007). A merging-based approach to handling inconsistency in locally prioritized software requirements. In Proceedings of the second Conference on knowledge science, engineering and management (KSEM’07) (pp. 103–114).
[84] Pigozzi, G. (2006). Belief merging and the discursive dilemma: An argument-based account to paradoxes of judgment aggregation. Synthese, 152(2), 285–298. · Zbl 1112.03305 · doi:10.1007/s11229-006-9063-7
[85] Pigozzi, G., & Hartmann, S. (2007). Judgment aggregation and the problem of truth-tracking. In Proceedings of the eleventh conference on theoretical aspects of rationality and knowledge (TARK’07) (pp. 248–252).
[86] Qi, G. (2007). A model-based approach for merging prioritized knowledge bases in possibilistic logic. In Proceedings of the AAAI conference on artificial intelligence (AAAI’07) (pp. 471–476).
[87] Qi, G., Liu, W., & Bell, D. A. (2006). Merging stratified knowledge bases under constraints. In Proceedings of the twenty-first AAAI conference on artificial intelligence (AAAI’06). · Zbl 1110.68144
[88] Rescher, N., & Manor, R. (1970). On inference from inconsistent premises. Theory and Decision, 1, 179–219. · Zbl 0212.31103 · doi:10.1007/BF00154005
[89] Revesz, P. Z. (1993). On the semantics of theory change: Arbitration between old and new information. In Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on principles of databases (pp. 71–92).
[90] Revesz, P. Z. (1997). Model-theoretic minimal chenge operators for constraint databases. In Proceedings of the sixth international conference on database theory (ICDT’97) (pp. 447–460).
[91] Revesz, P. Z. (1997). On the semantics of arbitration. International Journal of Algebra and Computation, 7(2), 133–160. · Zbl 0865.68040 · doi:10.1142/S0218196797000095
[92] Satterthwaite, M. (1975). Strategy-proofness and Arrow’s conditions. Journal of Economic Theory, 10, 187–217. · Zbl 0315.90088 · doi:10.1016/0022-0531(75)90050-2
[93] Smets, P. (1990). The combination of evidence in the transferable belief model. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(5), 447–458. · Zbl 05111385 · doi:10.1109/34.55104
[94] Spohn, W. (1987). Ordinal conditional functions: A dynamic theory of epistemic states. In W. L. Harper, & B. Skyrms (Eds.), Causation in decision, belief change, and statistics (Vol. 2., pp. 105–134).
[95] Zhang, D. (2005). A logical model for Nash bargaining solution. In Proceedings of the nineteenth international joint conference on artificial intelligence (IJCAI-05) (pp. 983–988).
[96] Zhang, D. (2007). Reasoning about bargaining situations. In Proceedings of the AAAI conference on artificial intelligence (AAAI’07) (pp. 154–159).
[97] Zhang, D., & Zhang, Y. (2008). An ordinal bargaining solution with fixed-point property. Journal of Artificial Intelligence Research, 33(1), 433–464. · Zbl 1165.91390
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.