Skip to main content
SpringerLink
Log in

Logic Based Merging

  • Published:
Journal of Philosophical Logic Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

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.

    Article  Google Scholar 

  2. Arieli, O. (2008). Distance-based paraconsistent logics. International Journal of Approximate Reasoning, 48(3), 766–783.

    Article  Google Scholar 

  3. Arrow, K., Sen, A. K., & Suzumura, K. (Eds.) (2002). Handbook of Social Choice and Welfare, Vol. 1. North-Holland.

  4. Arrow, K. J. (1963). Social choice and individual values (2nd ed.). New York: Wiley.

    Google Scholar 

  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.

    Article  Google Scholar 

  6. Baral, C., Kraus, S., & Minker, J. (1991). Combining multiple knowledge bases. IEEE Transactions on Knowledge and Data Engineering, 3(2), 208–220.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  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.

  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.

    Article  Google Scholar 

  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).

  14. Benferhat, S., Lagrue, S., & Rossit, J. (2009). Max-based prioritized information fusion without commensurability. Journal of Logic and Computation, 19(6), 1577–1610.

    Article  Google Scholar 

  15. Besnard, P., & Schaub, T. (1998). Signed systems for paraconsistent reasoning. Journal of Automated Reasoning, 20(1), 191–213.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  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).

  19. Booth, R. (2006). Social contraction and belief negotiation. Information Fusion, 7(1), 19–34.

    Google Scholar 

  20. Borgida, A. (1985). Language features for flexible handling of exceptions in information systems. ACM Transactions on Database Systems, 10, 563–603.

    Article  Google Scholar 

  21. Bovens, L., & Rabinowicz, W. (2006). Democratic answers to complex questions. An epistemic perspective. Synthese, 150, 131–153.

    Article  Google Scholar 

  22. Brams, S. J., & Fishburn, P. C. (1983). Approval voting. Springer Verlag.

  23. Chacón, J. L., & Pino Pérez, R. (2006). Merging operators: Beyond the finite case. Information Fusion, 7(1), 41–60.

    Google Scholar 

  24. Chopra, S., Ghose, A., & Meyer, T. (2006). Social choice theory, belief merging, and strategy-proofness. Information Fusion, 7(1), 61–79.

    Google Scholar 

  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).

  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).

  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.

    Google Scholar 

  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.

    Article  Google Scholar 

  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).

  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).

  34. Delgrande, J. P., & Schaub, T. (2007). A consistency-based framework for merging knowledge bases. Journal of Applied Logic, 5(3), 459–477.

    Article  Google Scholar 

  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).

  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.

  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.

    Article  Google Scholar 

  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).

  39. Everaere, P., Konieczny, S., & Marquis, P. (2007). The strategy-proofness landscape of merging. Journal of Artificial Intelligence Research, 28, 49–105.

    Google Scholar 

  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.

    Article  Google Scholar 

  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).

  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).

  44. Gärdenfors, P. (1988). Knowledge in flux. MIT Press.

  45. Gärdenfors, P. (Ed.) (1992). Belief revision. Cambridge University Press.

  46. Gauwin, O., Konieczny, S., & Marquis, P. (2007). Conciliation through iterated belief merging. Journal of Logic and Computation, 17(5), 909–937.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  49. Gorogiannis, N., & Hunter, A. (2008). Implementing semantic merging operators using binary decision diagrams. International Journal of Approximate Reasoning, 49(1), 234–251.

    Article  Google Scholar 

  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).

  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).

  54. Hunter, A. (2002). Logical fusion rules for merging structured news reports. Data & Knowledge Engineering, 42(1), 23–56.

    Article  Google Scholar 

  55. Hunter, A. (2002). Merging structured text using temporal knowledge. Data & Knowledge Engineering, 41(1), 29–66.

    Article  Google Scholar 

  56. Hunter, A., & Liu, W. (2006). Merging uncertain information with semantic heterogeneity in XML. Knowledge and Information Systems, 9(2), 230–258.

    Article  Google Scholar 

  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).

  58. Hunter, A., & Summerton, R. (2006). Merging news reports that describe events. Data & Knowledge Engineering, 59(1), 1–24.

    Article  Google Scholar 

  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).

  61. Katsuno, H., & Mendelzon, A. O. (1991). Propositional knowledge base revision and minimal change. Artificial Intelligence, 52, 263–294.

    Article  Google Scholar 

  62. Kelly, J. S. (1988). Social choice theory: An introduction. Springer-Verlag.

  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.

    Article  Google Scholar 

  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).

  66. Konieczny, S., Lang, J., & Marquis, P. (2004). DA2 merging operators. Artificial Intelligence, 157(1–2), 49–79.

    Article  Google Scholar 

  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.

    Google Scholar 

  69. Konieczny, S., & Pino Pérez, R. (2002). Merging information under constraints: A logical framework. Journal of Logic and Computation, 12(5), 773–808.

    Article  Google Scholar 

  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).

  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.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  77. Lin, J., & Mendelzon, A. O. (1998). Merging databases under constraints. International Journal of Cooperative Information System, 7(1), 55–76.

    Article  Google Scholar 

  78. Lin, J., & Mendelzon, A. O. (1999). Knowledge base merging by majority. In Dynamic worlds: From the frame problem to knowledge management.

  79. List, C., & Polak, B. (2010). Introduction to judgment aggregation. Journal of Economic Theory, 145(2), 441–466.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  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).

  88. Rescher, N., & Manor, R. (1970). On inference from inconsistent premises. Theory and Decision, 1, 179–219.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  92. Satterthwaite, M. (1975). Strategy-proofness and Arrow’s conditions. Journal of Economic Theory, 10, 187–217.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  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.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Centre de Recherche en Informatique de Lens (CRIL), CNRS, Faculté des Sciences, Université D’Artois, 62300, Lens, France

    Sébastien Konieczny

  2. Departamento de Matemáticas, Facultad de Ciencias, Universidad de Los Andes, Mérida, 5101, Venezuela

    Ramón Pino Pérez

Authors
  1. Sébastien Konieczny
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ramón Pino Pérez
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sébastien Konieczny.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Konieczny, S., Pino Pérez, R. Logic Based Merging. J Philos Logic 40, 239–270 (2011). https://doi.org/10.1007/s10992-011-9175-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10992-011-9175-5

Keywords

Search

Navigation