Logic Journal of IGPL Advance Access originally published online on June 7, 2009
Logic Journal of IGPL 2009 17(4):325-350; doi:10.1093/jigpal/jzp014
Distance-based non-deterministic semantics for reasoning with uncertainty
Department of Computer Science, The Academic College of Tel-Aviv, Israel.
E-mail: oarieli{at}mta.ac.il
Department of Computer Science, Tel-Aviv University, Israel.
E-mail: annaz{at}post.tau.ac.il
Non-deterministic matrices, a natural generalization of many-valued matrices, are semantic structures in which the value assigned to a complex formula may be chosen non-deterministically from a given set of options. We show that by combining non-deterministic matrices and distance-based considerations, one obtains a family of logics that are useful for reasoning with uncertainty. These logics are a conservative extension of those that are obtained by standard (i.e., deterministic) distance-based semantics, and so usual distance-based methods (in the context of, e.g., belief revision, information integration, and social choice theory) are easily simulated within our framework.
We investigate the basic properties of the distance-preferential non-deterministic logics, consider their application for reasoning with incomplete and inconsistent information, and show the correspondence between some particular entailments in our framework and well-known problems like max-SAT.
References
-
[1] Arenas M, Bertossi L, Chomicki J. Answer sets for consistent query answering in inconsistent databases. Theory and Practice of Logic Programming (2003) 3(4–5):393–424.[CrossRef][Web of Science]
[2] Arieli O. Distance-based paraconsistent logics. International Journal of Approximate Reasoning (2008) 48(3):766–783.[CrossRef][Web of Science]
[3] Arieli O. Reasoning with prioritized information by iterative aggregation of distance functions. Journal of Applied Logic (2008) 6(4):589–605.[CrossRef]
[4] Arieli O, Avron A. General patterns for nonmonotonic reasoning: from basic entailments to plausible relations. Logic Journal of the IGPL (2000) 8(2):119–148.[CrossRef]
[5] Arieli O, Denecker M, Bruynooghe M. Distance semantics for database repair. Annals of Mathematics and Artificial Intelligence (2007) 50(3–4):389–415.[CrossRef][Web of Science]
[6] Arieli O, Denecker M, Van Nuffelen B, Bruynooghe M. Computational methods for database repair by signed formulae. Annals of Mathematics and Artificial Intelligence (2006) 46(1–2):4–37.[CrossRef][Web of Science]
[7] Arieli O, Zamansky A. Reasoning with uncertainty by Nmatrix–Metric semantics. (2008) Springer. 69–82. In Proc. 15th Workshop on Logic, Language, Information and Computation (WoLLIC’ 08), LNAI 5110.
[8] Arieli O, Zamansky A. Some simplified forms of reasoning with distancebased entailments. In: Proc. 21st Canadian AI (2008) Springer. 36–47. LNAI 5032.
[9] Avron A. Non-deterministic semantics for logics with a consistency operator. International Journal of Approximate Reasoning (2007) 45:271–287.[CrossRef][Web of Science]
[10] Avron A, Konikowska B. Multi-valued calculi for logics based on non-determinism. Logic Journal of the IGPL (2005) 13(4):365–387.[CrossRef]
[11] Avron A, Ben Naim J, Konikowska B. Processing information from a set of sources. In: Trends in Logic, Towards Mathematical Philosophy (2009) 28. Springer. 165–184.
[12] Avron A, Lev I. Non-deterministic multi-valued structures. Journal of Logic and Computation (2005) 15:241–261.
[13] Avron A, Zamansky A. Many-valued non-deterministic semantics for first-order logics of formal inconsistency. In: Algebraic and Proof-theoretic Aspects of Non-classical Logics—Aguzzoli S, et al, eds. (2007) Springer. 1–24. LNAI 4460.
[14] Belnap N. A useful four-valued logic. Modern uses of multiple-valued logic (1977) 27:5–37.
[15] Ben Naim J. Lack of finite characterizations for the distance-based revision. In: Proc. KR’06 (2006) AAAI Press. 239–248.
[16] Carnielli W, Esteban M, Marcos J. Logics of formal inconsistency. In: Handbook of Philosophical Logic—Gabbay DM, Guenthner F, eds. (2007) 14, Second edition. Springer. 1–95.
[17] Carnielli W, Marcos J. A taxonomy of C-systems. In. In: Paraconsistency: The Logical Way to the Inconsistent—Carnielli WA, Coniglio ME, D'Ottaviano I, eds. (2002) Marcel Dekker. 1–94. number 228 in Lecture Notes in Pure and Applied Mathematics.
[18] Chomicki J. Consistent query answering: Five easy pieces. In. In: Proc. ICDT’07 (2007) Springer. 1. LNCS 4353.
[19] Chomicki J, Marchinkowski J. Minimal-change integrity maintenance using tuple deletion. Information and Computation (2005) 197(1–2):90–121.[CrossRef][Web of Science]
[20] Dalal M. Investigations into a theory of knowledge base revision. In: Proc. AAAI’88 (1988) AAAI Press. 475–479.
[21] Dubois D, Prade H. Belief change and possibility theory. In: Belief Revision—Gärdenfors P, ed. (1992) Cambridge Press. 142–182.
[22] Gabbay D. Theoretical foundation for non-monotonic reasoning, Part II: Structured non-monotonic theories. In: Proc. SCAI’91 (1991) IOS Press.
[23] Gottwald S. A Treatise on Many-Valued Logics, Studies in Logic and Computation (2001) 9. Baldock: Research Studies Press.
[24] Grove A. Two modellings for theory change. Journal of Philosophical Logic (1988) 17:157–180.[Web of Science]
[25] Konieczny S, Lang J, Marquis P. Distance-based merging: a general framework and some complexity results. In: Proc. KR’02 (2002) Morgan Kaufmann Publishers. 97–108.
[26] Konieczny S, Pino Pérez R. Merging information under constraints: a logical framework. Logic and Computation (2002) 12(5):773–808.[CrossRef]
[27] Kraus S, Lehmann D, Magidor M. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial Intelligence (1990) 44(1–2):167–207.[CrossRef][Web of Science]
[28] Lafage C, Lang J. Logical representation of preference for group decision making. In: Proc. KR’2000 (2000) Morgan Kaufmann Publishers. 457–468.
[29] Lafage C, Lang J. Propositional distances and preference representation. In: Proc. ECSQARU’01 (2001) Springer. 48–59. LNAI 2143.
[30] Lehmann D, Magidor M. What does a conditional knowledge base entail? Artificial Intelligence (1992) 55:1–60.[CrossRef][Web of Science]
[31] Lehmann D, Magidor M, Schlechta K. Distance semantics for belief revision. Journal of Symbolic Logic (2001) 66(1):295–317.[CrossRef][Web of Science]
[32] Lin J, Mendelzon AO. Knowledge base merging by majority. In: Dynamic Worlds: From the Frame Problem to Knowledge Management (1999) Kluwer.
[33] Lopatenko A, Bertossi L. Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics. In: Proc. ICDT’07 (2007) Springer. 179–193. LNCS 4353.
[34] Makinson D. General patterns in nonmonotonic reasoning. In. In: Handbook of Logic in Artificial Intelligence and Logic Programming—Gabbay D, Hogger C, Robinson J, eds. (1994) 3:35–110.
[35] Peppas P, Chopra S, Foo N. Distance semantics for relevance-sensitive belief revision. In: Proc. KR’04 (2004) AAAI Press. 319–328.
[36] Pigozzi G. Two aggregation paradoxes in social decision making: the Ostrogorski paradox and the discursive dilemma. Episteme (2005) 2(2):33–42.
[37] Rabaey JM, Chandrakasan A, Nikolic B. Digital Integrated Cicruits: A Design Perspective (2003) Prentice-Hall.
[38] Ravesz P. On the semantics of theory change: arbitration between old and new information. In: Proc. PODS’93 (1993) ACM Press. 71–92.
[39] Shoham Y. Reasoning about Change (1988) MIT Press.
[40] Spohn W. Ordinal conditional functions: a dynamic theory of epistemic states. In: Belief Change and Statistics (1988) II. Kluwer. 105–134.
[41] Tarski A. Introduction to Logic (1941) Oxford University Press.
[42] Troelstra AS, Schwichtenberg H. Basic Proof Theory (2000) Cambridge University Press.
[43] Urquhart A. Many-valued logic. In: Handbook of Philosophical Logic—Gabbay D, Guenthner F, eds. (2001) II. Kluwer. 249–295.
CiteULike 
Connotea 
Del.icio.us What's this?
| ||||||||||||||||||||||||||||||||||||||||||||||||