Skip to main content
SpringerLink
Log in

Reasoning about Minimal Knowledge in Nonmonotonic Modal Logics

  • Published:
Journal of Logic, Language and Information Aims and scope Submit manuscript

Abstract

We study the problem of embedding Halpern and Moses's modal logic of minimal knowledge states into two families of modal formalism for nonmonotonic reasoning, McDermott and Doyle's nonmonotonic modal logics and ground nonmonotonic modal logics. First, we prove that Halpern and Moses's logic can be embedded into all ground logics; moreover, the translation employed allows for establishing a lower bound (Π3p) for the problem of skeptical reasoning in all ground logics. Then, we show a translation of Halpern and Moses's logic into a significant subset of McDermott and Doyle's formalisms. Such a translation both indicates the ability of Halpern and Moses's logic of expressing minimal knowledge states in a more compact way than McDermott and Doyle's logics, and allows for a comparison of the epistemological properties of such nonmonotonic modal formalisms.

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

  • Cadoli, M. and Schaerf, M., 1993, “A survey of complexity results for nonmonotonic logics,” Journal of Logic Programming 17, 127–160.

    Google Scholar 

  • Donini, F.M., Nardi, D., and Rosati, R., 1995, “Non-first-order features in concept languages,” pp. 91–102 in Proceedings of AI*IA-95, G. Soda, ed., Lecture Notes in Artificial Intelligence, Vol. 992, Berlin: Springer-Verlag.

    Google Scholar 

  • Donini, F.M., Nardi, D., and Rosati, R., 1997, “Ground nonmonotonic modal logics,” Journal of Logic and Computation 7(4), 523–548.

    Google Scholar 

  • Eiter, T. and Gottlob, G., 1995, “On the computational cost of disjunctive logic programming: Propositional case,” Annals of Mathematics and Artificial Intelligence 15(3, 4), 289–323.

    Google Scholar 

  • Engelfriet, J., 1996, “Minimal temporal epistemic logic,” Notre Dame Journal of Formal Logic 37(2), 233–259.

    Google Scholar 

  • Gottlob, G., 1992, “Complexity results for nonmonotonic logics,” Journal of Logic and Computation 2, 297–425.

    Google Scholar 

  • Gottlob, G., 1993, “Translating default logic into standard autoepistemic logic,” Journal of ACM 42(4), 711–740.

    Google Scholar 

  • Halpern, J.Y. and Moses, Y., 1985, “Towards a theory of knowledge and ignorance: Preliminary report,” Technical Report CD-TR 92/34, IBM.

  • Hughes, G.E. and Cresswell, M.J., 1968, An Introduction to Modal Logic, London: Methuen.

    Google Scholar 

  • Johnson, D.S., 1990, “A catalog of complexity classes,” pp. 67–161 in Handbook of Theoretical Computer Science, Vol. A, J. van Leeuwen, ed., Amsterdam: Elsevier Science Publishers/North Holland.

    Google Scholar 

  • Konolige, K., 1988, “On the relationship between default and autoepistemic logic,” Artificial Intelligence Journal 35, 343–382.

    Google Scholar 

  • Lifschitz, V., 1991, “Nonmonotonic databases and epistemic queries,” pp. 381–386 in Proceedings of IJCAI-91, Sydney, D. Driankow, P.W. Eklund, and A.L. Ralescu, eds., Berlin: Springer-Verlag.

    Google Scholar 

  • Lin, F. and Shoham, Y., 1992, “Epistemic semantics for fixed-point non-monotonic logics,” Artificial Intelligence Journal 57, 271–289.

    Google Scholar 

  • Lin, F. and Shoham, Y., 1998, “On non-forgetting and minimal learning,” in Proceedings of the 1993. International Colloquium on Cognitive Science, N. Asher, K. Korta, and J. Ezquerro, eds., Dordrecht: Kluwer Academic Publishers, to appear.

    Google Scholar 

  • Marek, W. and Truszczyński, M., 1993, Nonmonotonic Logics - Context-Dependent Reasoning, Berlin: Springer-Verlag.

    Google Scholar 

  • McDermott, D., 1982, “Non-monotonic logic II: Non-monotonic modal theories,” Journal of the ACM 29, 33–57.

    Google Scholar 

  • McDermott, D. and Doyle, J., 1980, “Non-monotonic logic I,” Artificial Intelligence Journal 13, 41–72.

    Google Scholar 

  • Meyer, J.-J.Ch. and van der Hoek, W., 1995a, “A default logic based on epistemic states,” Fundamenta Informaticae 23(1) 33–65.

    Google Scholar 

  • Meyer, J.-J.Ch. and van der Hoek, W., 1995b, Epistemic Logic for AI and Computer Science, Cambridge: Cambridge University Press.

    Google Scholar 

  • Moore, R.C., 1985, “Semantical considerations on nonmonotonic logic,” Artificial Intelligence Journal 25, 75–94.

    Google Scholar 

  • Nardi, D. and Rosati, R., 1995, “A preference semantics for ground nonmonotonic modal logics,” pp. 225–236 in Proceedings of EPIA-95, C. Pinto-Ferreira and N. Mamede, eds., Lecture Notes in Artificial Intelligence, Vol. 990, Berlin: Springer-Verlag.

    Google Scholar 

  • Rosati, R., 1997a, “Reasoning with minimal belief and negation as failure: Algorithms and complexity,” pp. 430–435 in Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI-97), Cambridge, MA: MIT Press.

    Google Scholar 

  • Rosati, R., 1997b, “Complexity of only knowing: The propositional case,” pp. 76–91 in Proceedings of the Fourth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR-97), J. Dix, U. Furbach, and A. Nerode, eds., Lecture Notes in Artificial Intelligence, Vol. 1265, Berlin: Springer-Verlag.

    Google Scholar 

  • Schwarz, G., 1990, “Autoepistemic modal logics,” pp. 97–109 in Proceedings of TARK-90, R. Parikh, ed., San Mateo, CA: Morgan Kaufmann.

    Google Scholar 

  • Schwarz, G., 1991, “Autoepistemic logic of knowledge,” pp 260–274 in Proceedings of LPNMR-91, A. Nerode, V. Marek, and V.S. Subrahmanien, eds., Cambridge, MA: MIT Press.

    Google Scholar 

  • Schwarz, G., 1992a, “Minimal model semantics for nonmonotonic modal logics,” pp. 34–43 in Proceedings of LICS-92, New York: IEEE Computer Society Press.

    Google Scholar 

  • Schwarz, G., 1992b, “Bounding introspection in nonmonotonic logics,” pp. 581–590 in Proceedings of KR-92, B. Nebel, C. Rich, and W. Swertout, eds., Los Altos, CA: Morgan Kaufmann.

    Google Scholar 

  • Schwarz, G. and Truszczyński, M., 1994, “Minimal knowledge problem: A new approach,” Artificial Intelligence Journal 67, 113–114.

    Google Scholar 

  • Segerberg, K., 1971, An Essay in Classical Modal Logic, Filosofiska Studier, Vol. 13, Uppsala, Sweden: Uppsala University.

    Google Scholar 

  • Shoham, Y., 1987, “Nonmonotonic logics: Meaning and utility,” pp. 388–392 in Proceedings of IJCAI-87, J. McDermott, ed., San Mateo, CA: Morgan Kaufmann.

    Google Scholar 

  • Tiomkin, M. and Kaminski, M., 1990, “Nonmonotonic default modal logics,” pp. 73–84 in Proceedings of TARK-90, R. Parikh, ed., San Mateo, CA: Morgan Kaufmann.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Informatica e Sistemistica, Università di Roma “La Sapienza”, Via Salaria 113, 00198, Roma, Italy (E-mail

    Riccardo Rosati

Authors
  1. Riccardo Rosati
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Rosati, R. Reasoning about Minimal Knowledge in Nonmonotonic Modal Logics. Journal of Logic, Language and Information 8, 187–203 (1999). https://doi.org/10.1023/A:1008277218820

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1008277218820

Search

Navigation