Proceedings

Computing Strongest Necessary and Weakest Sufficient Conditions of First-Order Formulas

Download BibTeX Cite

Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 145-153.

© 2001 International Joint Conferences on Artificial Intelligence

Abstract

A technique is proposed for computing the weakest sufficient (wsc) and strongest necessary (snc) conditions for formulas in an expressive fragment of first-order logic using quantifier elimination techniques. The efficacy of the approach is demonstrated by using the techniques to compute snc’s and wsc’s for use in agent communication applications, theory approximation and generation of abductive hypotheses. Additionally, we generalize recent results involving the generation of successor state axioms in the propositional situation calculus via snc’s to the first-order case. Subsumption results for existing approaches to this problem and a re-interpretation of the concept of forgetting as a process of quantifier elimination are also provided.

  1. [Abiteboul et al., 1996] S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley Pub. Co., 1996.
  2. [Brown, 1990] F.M. Brown. Boolean Reasoning. Kluwer Academic Publishers, Dordrecht, 1990.
  3. [Cadoli, 1995] M. Cadoli. Tractable Reasoning in Artificial Intelligence, volume 941 of LNAI. Springer-Verlag, Berlin Heidelberg, 1995.
  4. [Dijkstra, 1976] E. W Dijkstra. A Discipline of Program- ming. Prentice-Hall, 1976.
  5. [Doherty et al., 1996] P. Doherty, W. Lukaszewicz, and A. Szalas. A reduction result for circumscribed semi- Horn formulas. Fundamenta Informaticae, 28(3-4):261- 271, 1996.
  6. [Doherty et al., 1997] P. Doherty, W. Lukaszewicz, and A. Szalas. Computing circumscription revisited. Journal of Automated Reasoning, 18(3):297-336, 1997.
  7. [Doherty et al., 1998] P. Doherty, W. Lukaszewicz, and A. Szalas. General domain circumscription and its effec- tive reductions. Fundamenta Informaticae, 36(1):23-55, 1998.
  8. [Ebbinghaus and Flum, 1995] H-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer-Verlag, Heidel- berg, 1995.
  9. [Kautz and Selman, 1996] H. Kautz and B. Selman. Knowl- edge compilation and theory approximation. Journal of the ACM, 43(2):193-224, 1996.
  10. [Lin and Reiter, 1994] F. Lin and R. Reiter. Forget it! In R. Greiner and D. Subramanian, editors, Working Notes of AAAI Fall Symposium on Relevance, pages 154-159, Menlo Park, Ca., 1994. AAAI.
  11. [Lin and Reiter, 1997] F. Lin and R. Reiter. How to progress a database. Artificial Intelligence, 92(1-2):131-167, 1997.
  12. [Lin, 2000] F. Lin. On strongest necessary and weakest suffi- cient conditions. In A.G. Cohn, F. Giunchiglia, and B. Sel- man, editors, KR2000, pages 167-175, 2000.
  13. [McCarthy, 2000] J. McCarthy. Approximate objects and ap- proximate theories. In A.G. Cohn, F. Giunchiglia, and B. Selman, editors, KR2000, pages 519-526, 2000.
  14. [Nonnengart and Szalas, 1998] A. Nonnengart and A. Sza- las. A fixpoint approach to second-order quantifier elim- ination with applications to correspondence theory. In E. Orlowska, editor, Logic at Work: Essays Dedicated to the Memory of Helena Rasiowa, volume 24 of Studies in Fuzziness and Soft Computing, pages 307-328. Springer Physica-Verlag, 1998.
  15. [Nonnengart et al., 1999] A. Nonnengart, H.J. Ohlbach, and A. Szalas. Elimination of predicate quantifiers. In H.J. Ohlbach and U. Reyle, editors, Logic, Language and Rea- soning. Essays in Honor of Dov Gabbay, Part I, pages 159-181. Kluwer, 1999.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards