Two Approaches to Efficient Open-World Reasoning

  • Giuseppe De Giacomo
  • Hector Levesque
Part of the The Springer International Series in Engineering and Computer Science book series (SECS, volume 597)


We show how a simple but efficient evaluation procedure that is logically correct only for closed-world knowledge bases can nonetheless be used in certain contexts with open-world ones. We discuss two cases, one based on restricting queries to be in a certain normal form, and the other, arising in reasoning about actions, based on having sensing information at the right time so as to dynamically reduce open-word reasoning to closed-word reasoning.


Automated reasoning computational tractability open-world database closed-world database incomplete knowledge sensing information 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. Abiteboul, S. and Duschka, O. (1998). Complexity of answering queries using materialized views. In Proc. of the 17th ACM SIGACT SIGMOD SIGART Sym. On Principles of Database Systems (PODS’98), pages 254–265.Google Scholar
  2. Baral, C. and Son, T. (1997). Approximate reasoning about actions in presence of sensing and incomplete information. In Proc. of the 1997 Int. Logic Programming Symposium (ILPS’97), pages 387–401.Google Scholar
  3. Belnap, N. (1977). A useful four-valued logic. In Dunn, J. and Epstein, G., editors, Modern uses of multiple-valued logic, pages 8–37. Reidel Publishing Company.Google Scholar
  4. Blake, A. (1938). Canonical expressions in Boolean algebra. PhD thesis, University of Chicago.Google Scholar
  5. Cadoli, M. and Schaerf, M. (1992). Approximate reasoning and non-omniscient agents. In Proc. of the 4th Conf on Theoretical Aspects of Reasoning about Knowledge (TARK’92), pages 169–183. Morgan Kaufmann Publishers.Google Scholar
  6. Chandra, A. K. and Merlin, P. M. (1977). Optimal implementation of conjunctive queries in relational data bases. In Proc. of the 9th ACM Sym. on Theory of Computing (STOC’77), pages 77–90.Google Scholar
  7. De Giacomo, G. and Levesque, H. (1999). Projection using regression and sensors. In Proc. of the 16th Int. Joint Conf. on Artificial Intelligence (IJ-CAI’99), pages 160–165.Google Scholar
  8. Dunn, M. (1976). Intuitive semantics for first-degree entailments and coupled trees. Philosophical Studies, 29:149–168.MathSciNetCrossRefGoogle Scholar
  9. Ginsberg, M. (1988). Multivalued logics: a uniform approach to reasoning in artificial intelligence. Computational Intelligence, 4:265–316.CrossRefGoogle Scholar
  10. Golden, K. and Weld, D. (1996). Representing sensing actions: the middle ground revisited. In Proc. of the 5th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR’96), pages 174–185.Google Scholar
  11. Grahne, G. and Mendelzon, A. (1999). Tableau techniques for querying information sources through global schemas. In Proc. of the 7th Int. Conf. on Database Theory (ICDT’99), volume 1540 of Lecture Notes in Computer Science, pages 332–347. Springer-Verlag.Google Scholar
  12. Hogg, T., Huberman, B., and Williams, C. (1996). Frontiers in problem solving: phase transitions and complexity. Artificial Intelligence, 81(1–2): 1–15.MathSciNetCrossRefGoogle Scholar
  13. Imielinski, T. and Lipski, W. (1984). Incomplete information in relational databases. Journal of ACM, 31(4):761–791.MathSciNetzbMATHCrossRefGoogle Scholar
  14. Kautz, H., McAllester, D., and Selman, B. (1996). Encoding plans in propositional logic. In Proc. of the 5th Int. Conf on the Principles of Knowledge Representation and Reasoning (KR’96), pages 374–384.Google Scholar
  15. Lakemeyer, G. (1990). Models of belief for decidable reasoning in incomplete knowledge bases. PhD thesis, Department of Computer Science, University of Toronto.Google Scholar
  16. Levesque, H. (1984). A logic of implicit and explicit belief. In Proc. of the 4th Nat. Conf. on Artificial Intelligence (AAAI’84), pages 198–202.Google Scholar
  17. Levesque, H. (1986). Making believers out of computers. Artificial Intelligence, 30:81–108.MathSciNetCrossRefGoogle Scholar
  18. Levesque, H. (1996). What is planning in the presence of sensing? In Proc. of the 13th Nat. Conf. on Artificial Intelligence (AAAI’96), pages 1139–1146.Google Scholar
  19. Levesque, H. (1998). A completeness result for reasoning with incomplete first-order knowledge bases. In Proc. of the 6th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR’98), pages 14–23.Google Scholar
  20. Levy, A. Y., Mendelzon, A. O., Sagiv, Y., and Srivastava, D (1995). Answering queries using views. Proc. of the 14th ACM SIGACT SIGMOD SIGART Sym. on Principles of Database Systems (PODS’95), pages 95–104.Google Scholar
  21. Levesque, H., Reiter, R., Lespérance, Y., Lin, F., and Scherl, R. (1997). GOLOG: A logic programming language for dynamic domains. Journal of Logic Programming, 31:59–84.MathSciNetzbMATHCrossRefGoogle Scholar
  22. Lin, F. and Reiter, R. (1994). State constraints revisited. Journal of Logic and Computation, 4(5):655–678.MathSciNetzbMATHCrossRefGoogle Scholar
  23. McCarthy, J. (1968). Programs with common sense. In Minsky, M., editor, Semantic Information Processing, pages 403–418. The MIT Press.Google Scholar
  24. McCarthy, J. and Hayes, P. (1969). Some philosophical problems from the standpoint of artificial intelligence. Machine Intelligence, 4:463–502.zbMATHGoogle Scholar
  25. Parkes, A. (1999). Lifted search engines for satisfiability. PhD thesis, Dept. of Computer and Information Science, University of Oregon.Google Scholar
  26. Patel-Schneider, P. (1985). A decidable first-order logic for knowledge representation. In Proc. of the 9th Int. Joint Conf on Artificial Intelligence (IJCAI’85), pages 455–458.Google Scholar
  27. Poole, D. (1995). Logic programming for robot control. In Proc. of the 14th Int. Joint Conf. on Artificial Intelligence (IJCAr95), pages 150-157.Google Scholar
  28. Reiter, R. (1984). Towards a logical reconstruction of relational database theory. In Brodie, M. L., Mylopoulos, J., and Schmidt, J. W., editors, On Conceptual Modelling. Springer-Verlag.Google Scholar
  29. Reiter, R. (1991). The frame problem in the situation calculus: A simple solution (sometimes) and a completeness result for goal regression. InArtificial Intelligence and Mathematical Theory of Computation: Papers in Honor of John McCarthy, pages 359–380. Academic Press.Google Scholar
  30. Reiter, R. (2000). Knowledge in Action: Logical Foundation for Describing and Implementing Dynamical Systems. Kluwer. In preparation.Google Scholar
  31. Selman, B., Levesque, H., and Mitchell, D. (1992). A new method for solving hard instances of satisfiability. In Proc. of the 10th Nat. Conf. on Artificial Intelligence (AAAI’92), pages 440–446.Google Scholar
  32. Urquhart, A. (1986). Many-valued logic. In Gabbay, D. and Guenthner, F., editors, Handbook of philosophical logic, volume III, pages 71–116. Reidel Publishing Company.Google Scholar
  33. Van Fraasen, B. (1966). Singular terms, truth-value gaps, and free logic. Journal of philosophical logic, 63:481–495.Google Scholar
  34. Vardi, M. (1985). Querying logical databases. In Proc. of the 4th ACM SIGACT SIGMOD Sym. on Principles of Database Systems (PODS’S5), pages 57–65.CrossRefGoogle Scholar
  35. Vassiliou, Y. (1980). A formal treatment of incomplete information in database management. PhD thesis, Department of Computer Science, University of Toronto.Google Scholar
  36. Weld, D., Anderson, C., and Smith, D. (1998). Extending graphplan to handle uncertainty and sensing actions. In Proc. of the 15th Nat. Conf. on Artificial Intelligence (AAAI’98), pages 897–904.Google Scholar

Copyright information

© Springer Science+Business Media New York 2000

Authors and Affiliations

  • Giuseppe De Giacomo
    • 1
  • Hector Levesque
    • 2
  1. 1.Dipartimento di Informatica e SistemisticaUniversità di Roma “La Sapienza”RomeItaly
  2. 2.Department of Computer ScienceUniversity of TorontoTorontoCanada

Personalised recommendations