Knowledge, Time, and the Problem of Logical Omniscience

• Autorzy: Wang R-J.
• Języki publikacji: EN

Abstrakty

EN

It is well known that Modal Epistemic logic (MEL) suffers from the problem of logical omniscience. In this paper, we will argue that in order to solve the problem, the temporal dimension of knowledge has to be revealed and following this analysis, we present a general epistemic framework, timed Modal Epistemic Logic (tMEL), modified from MEL, such that the time at which a formula is known by an agent based on his reasoning procedure is explicitly stated. With the help of the additional temporal devices, we are able to determine what is actually known by the agent within a reasonable time of reasoning. The discussions will focus on tS4, the tMEL counterpart of S4, but the method can be uniformly generalized to the study of other tMEL logics. Both the semantics and axiomatic proof systems will be provided, accompanied by soundness and completeness results, and other technical features of tMEL are also examined. This work originates from the study of Justification Logic, which shapes many aspects of this paper, and is also a direct response to the request to utilize the use of awareness functions such that time can be added to the picture. A generalized awareness function is employed in the semantics to trace when a formula is deduced.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 106, nr 2-4
• Strony: 321--338
• Opis fizyczny: Bibliogr. 36 poz.

Twórcy

autor

Wang R-J.

• Computer Science, CUNY Graduate Center, 365 Fifth Avenue, New York, NY 10016, USA,

Bibliografia

• [1] Artemov, S. N.: Operational modal logic, Technical Report MSI 95-29, Cornell University, 1995.
• [2] Artemov, S. N.: Explicit provability and constructive semantics, Bulletin of Symbolic logic, 7(1), 2001, 1-36.
• [3] Artemov, S. N.: Justified common knowledge, Theoretical Computer Science, 357(1), 2006, 4-22.
• [4] Artemov, S. N.: The Logic of Justification, The Review of Symbolic Logic, 1(4), December 2008, 477-513.
• [5] Artemov, S. N., Kuznets, R.: Logical Omniscience Via Proof Complexity, in: Computer Science Logic, 20th International Workshop, CSL 2006, 15th Annual Conference of the EACSL, Szeged, Hungary, September 25-29, 2006, Proceedings (Z. ésik, Ed.), vol. 4207 of Lecture Notes in Computer Science, Springer, 2006, 135-149.
• [6] Artemov, S. N., Nogina, E.: Introducing Justification into Epistemic Logic, Journal of Logic and Computation, 15(6), 2005, 1059-1073.
• [7] Brezhnev, V., Kuznets, R.: Making knowledge explicit: How hard it is, Theoretical Computer Science, 357, 2006, 23-34.
• [8] Chellas, B. F.: Modal logic, Cambridge University Press, 1980.
• [9] Chomsky, N.: On the Generative enterprise: a discussion with R. Huybregts and H. van Riemsdijk, Dordrecht/ Cinnaminson: Foris, 1982.
• [10] Eberle, R. A.: A logic of believing, knowing, and inferring, Synthese, 26(3), 1974, 356-382.
• [11] Fagin, R., Halpern, J. Y.: Belief, awareness, and limited reasoning, Artificial Intelligence, 34, 1988, 39-76.
• [12] Fagin, R., Halpern, J. Y., Moses, Y., Vardi, M. Y.: Reasoning about knowledge, MIT Press, 1995.
• [13] Feferman, S., Ed.: Kurt G¨odel Collected Works, Oxford, 1986-2003, 5 volumes.
• [14] Fitting, M. C.: A logic of explicit knowledge, In L. Behounek and M. Bilkova (Eds.), Logica Yearbook 2004, Filosophia, 2005.
• [15] Fitting, M. C.: The logic of proofs, semantically, Annals of Pure and Applied Logic, 132, 2005, 1-25.
• [16] Gödel, K.: Vortrag bei Zisel, Translated as Lecture at Zisel's in [13] III, 62-113, 1938.
• [17] Halpern, J. Y., Pucella, R.: Dealing with logical omniscience, Proceedings of the 11th conference on Theoretical aspects of rationality and knowledge, 2007.
• [18] Hintikka, J.: Knowledge and Belief: An Introduction to the Logic of the Two Notions, Cornell University Press, 1962.
• [19] Hintikka, J.: Reasoning about knowledge in philosophy: the paradigm of epistemic logic, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, Morgan Kaufmann Publishers Inc., Monterey, California, United States, 1986.
• [20] Hocutt, M.: Is Epistemic Logic Possible?, Notre Dame Journal of Formal Logic, 13, 1972, 433-453.
• [21] Konolige, K.: A Deduction Model of Belief, Morgan Kaufmann, San Francisco, 1986.
• [22] Krupski, N. V.: On the complexity of the reflected logic of proofs, Theoretical Computer Science, 357(1), 2006, 136-142.
• [23] Levesque, H.: A logic of implicit and explicit belief, Proceedings AAAI-84, Austin, TX, 1984.
• [24] Mkrtychev, A.: Models for the Logic of Proofs, LFCS (S. I. Adian, A. Nerode, Eds.), 1234, Springer, 1997.
• [25] Montague, R.: Universal Grammar, Theoria, 36, 1970, 373-98.
• [26] Moore, R. C., Hendrix, G.: Computational models of beliefs and the semantics of belief sentences, Technical Report Technical Note 187, SRI International, 1979.
• [27] Moreno, A.: Avoiding Logical omniscience and perfect reasoning: A survey, AI Communications, 11(2), 1998, 101-122.
• [28] Pacuit, E.: A note on some explicit modal logics, Proceedings of the Fifth Panhellenic Logic Symposium, 2005.
• [29] Parikh, R.: Logical Omniscience, LCC '94: Selected Papers from the International Workshop on Logical and Computational Complexity, Springer-Verlag, London, UK, 1995.
• [30] Parikh, R.: Sentences, belief and logical omniscience, or what does deduction tell us?, The Review of Symbolic Logic, 1(04), 2009, 459-476.
• [31] Rantala, V.: Impossible worlds semantics and logical omniscience, Acta Philosophica Fennica, 35, 1982, 18-24.
• [32] Rubtsova, N.: Evidence Reconstruction of Epistemic Modal Logic S5, CSR (D. Grigoriev, J. Harrison, E. A. Hirsch, Eds.), 3967, Springer, 2006.
• [33] Scott, D.: Advice in modal logic, in: Philosophical Problems in Logic (K. Lambert, Ed.), Reidel, 1970.
• [34] Vardi,M. Y.: On epistemic logic and logical omniscience, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, 1986.
• [35] Wang, R.-J.: On Proof Realization On Modal logic, Technical Report TR-2009003, CUNY Ph.D. Program in Computer Science, 2009.
• [36] vonWright, G. H.: An Essay in Modal Logic, North Holland Publishing Co., Amsterdam, 1951.