Proceedings

Automated Reasoning: Past Story and New Trends

Download BibTeX Cite

Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 1607-1611.

© 2003 International Joint Conferences on Artificial Intelligence

Abstract

We overview the development of first-order automated reasoning systems starting from their early years. Based on the analysis of current and potential applications of such systems, we also try to predict new trends in first-order automated reasoning. Our presentation will be centered around two main motives: efficiency and usefulness for existing and future potential applications. This paper expresses the views of the author on past, present, and future of theorem proving in first-order logic gained during ten years of working on the development, implementation, and applications of the theorem prover Vampire, see [Riazanov and Voronkov, 2002a]. It reflects our recent experience with applications of Vampire in verification, proof assistants, theorem proving, and semantic Web, as well as the analysis of future potential applications.

  1. Afshordel et al., 2001) B. Afshordel, T. Hillenbrand, and C. Wei - denbach. First-order atom definitions extended. In R. Nieuwenhuis and A. Voronkov, editors, LPAR 2001 , volume 2050 of LNAI, pages 309-319. Springer Verlag, 200 I.
  2. Appel, 2001)
  3. A.W. Appel. Foundational proof-carrying code. In LICS 200/, pages 247-258, 2001.
  4. Baader and Schulz, 1996) F. Baader and K.U. Schulz. Unification in the union of disjoint equational theories: Combining decision pro- cedures. Journal of Symbolic Computations, 21:211-243, 1996.
  5. Bachmair and Ganzinger, 1994a) L. Bachmair and H. Ganzinger. Rewrite-based equational theorem proving with selection and sim- plification. Journal of Logic and Computation, 4(3) :217-247, 1994.
  6. Bachmair and Ganzinger, 1994b) L. Bachmair and H. Ganzinger. Rewrite techniques for transitive relations. In LICS'94. IEEE Com- puter Society Press, 1994.
  7. Bachmair and Ganzinger, 2001) L. Bachmair and H. Ganzinger. Resolution theorem proving. In A. Robinson and A. Voronkov, edi- tors, Handbook of Automated Reasoning, volume I, chapter 2, pages 19-99. Elsevier Science, 2001.
  8. Bachmair et at., 1993)
  9. L. Bachmair, T. Chen, and I.V. Ramakrish- nan. Associative-commutative discrimination nets. In M.-C. Gaudel and J.-P. Jouannaud, editors, TAPSOFT'93, volume 668 of LNCS, pages 61-74. Springer Verlag, 1993.
  10. Baumgartner, 2000)
  11. P. Baumgartner. FDPLL-a first-order Davis- Putnam-Logemann-Loveland procedure. In D. McAIIester, editor, CADE-17, volume 1831 of LNAI, pages 200-219. Springer Verlag, 2000.
  12. Brand, 1975)
  13. D. Brand. Proving theorems with the modification method. SIAM Journal of Computing, 4:412--430, 1975.
  14. de Nivelle et al., 2000) H. de Nivelle, R.A. Schmidt, and U. Hus- tad!. Resolution-based methods for modal logics. Logic Journal of the IGPL, 8(3):265-292, 2000.
  15. de Nivelle, 2000) H. de Nivelle. Bliksem 1.10 User's Manual. MPI fiir Informatik, Saarbriicken, 2000.
  16. Degtyarev and Voronkov, 2001) A. Degtyarev and A. Voronkov. Equality reasoning in sequent-based calculi . In A. Robinson and A. Voronkov, editors, Handbook of Automated Reasoning, volume I, chapter 10, pages 611-706. Elsevier Science, 2001.
  17. Degtyarev et al., 2002) A. Degtyarev, R. Nieuwenhuis, and A. Voronkov. Stratified resolution. Journal of Symbolic Computa- tions, pages 1-24, 2002. to appear.
  18. Denzinger and Fuchs, 1999) J. Denzinger and D. Fuchs. Coopera- tion of heterogeneous provers. InT. Dean, editor, ?roc. (/JCAI-99), volume 1, pages 10-15, 1999. IJCAI
  19. Denzinger et at., 1997) J. Denzinger, M. Kranenburg, and S. Schulz. DISCOUNT -a distributed and learning equa- tional prover. Journal of Automated Reasoning, 18(2):189-198, 1997.
  20. Ganzinger et al., 2001)
  21. H. Ganzinger, R. Nieuwenhuis, and P. Nivela. The Saturate system. Max-Planck Institute fiir Infor- matik, 200 I.
  22. Gordon and Melham, 1993)
  23. M. Gordon and T. Melham. Introduc- tion to HOL. Cambridge University Press, 1993.
  24. Graf, 1996)
  25. P. Graf. Term Indexing, volume 1053 of LNCS. Springer Verlag, 1996. [Hahnle, 200 I)
  26. R. Hahn! e. Tableaux and related methods. In A. Robinson and A. Voronkov, editors, Handbook of Automated Reasoning, volume I, chapter 3, pages 100-178. Elsevier Science, 2001.
  27. IEEE SUO-KIF project, 2002) IEEE SUO-KIF project. Standard upper ontology knowledge interchange format, 2002.
  28. Knuth and Bendix, 1970)
  29. D. Knuth and P. Bendix. Simple word problems in universal algebras. In J. Leech, editor, Computational Problems in Abstract Algebra, pages 263-297. Pergamon Press, Ox- ford, 1970.
  30. Letz and Stenz, 2001) R. Letz and G. Stenz. Model elimination and connection tableau procedures. In A. Robinson and A. Voronkov, editors, Handbook of Automated Reasoning, volume II, chapter 28, pages 2015-2114. Elsevier Science, 2001.
  31. Lusk, 1992)
  32. E.L. Lusk. Controlling redundancy in large search spaces: Argonne-style theorem proving through the years. In A. Voronkov, editor, LPAR'92., volume 624 of LNAI, pages 96--106, 1992.
  33. McCune and Padmanabhan, 1996) W. McCune and R. Padmanab- han. Automated Deduction in Equational Logic and Cubic Curves, volume 1095 of LNAI. Springer Verlag, 1996.
  34. McCune, 1994)
  35. W.W. McCune. OTTER 3.0 reference manual and guide. Technical Report ANL-94/6, Argonne National Laboratory, 1994.
  36. McCune, 1997)
  37. W. McCune. Solution of the robbins problem. Jour- nal of Automated Reasoning, 19(3):263-276, 1997.
  38. McMath et at., 2001) D. McMath, M. Rozenfeld, and R. Sommer. A computer environment for writing ordinary mathematical proofs. In R. Nieuwenhuis and A. Voronkov, editors, LPAR 200I, volume 2050 of LNAI, pages 502-511. Springer Verlag, 2001.
  39. Moser et at., 1997)
  40. M. Moser, 0. Ibens, R. Letz, J. Steinbach, C. Goller, J. Schumann, and K. Mayr. SETHEO and E-SETHEO- the CADE-13 systems. Journal of Automated Reasoning, 18:237- 246, 1997.
  41. M.P. Bonacina, 1994) W.W. McCune M.P. Bonacina. Distributed theorem proving by peers. In A. Bundy, editor, CADE-12, volume 814 of LNAI, pages 841-845, 1994.
  42. Necu1a and Lee, 2000)
  43. G.C. Necula and P. Lee. Proof generation in the Touchstone theorem prover. In D. McAIIester, editor, CADE-I7, volume 1831 of LNAI, pages 25-44. Springer Verlag, 2000.
  44. Nelson and Oppen, 1979) G. Nelson and D.C. Oppen. Simplifica- tion by cooperating decision procedures. ACM Transactions on Pro- gramming Languages and Systems, 1(2):245-257, 1979.
  45. Nieuwenhuis and Rubio, 2001) R. Nieuwenhuis and A. Rubio. Paramodulation-based theorem proving. In A. Robinson and A. Voronkov, editors, Handbook of Automated Reasoning, volume I, chapter 7, pages 371-443. Elsevier Science, 2001.
  46. Nieuwenhuis et al., 2001) R. Nieuwenhuis, T. Hillenbrand, A. Ri- azanov, and A. Voronkov. On the evaluation of indexing techniques for theorem proving. In R. Gore, A. Leitsch, and T. Nipkow, edi- tors, /JCAR 200/, volume 2083 of LNAI, pages 257-271. Springer Verlag, 200 I.
  47. Paulson, 2002)
  48. L.C. Paulson. The Isabelle Reference Manual. Cam- bridge University, 2002.
  49. Pfenning and Schuermann, 1998) F. Pfenning and C. Schuermann. Twelf User's Guide, 1998.
  50. Riazanov and Voronkov, 2002a) A. Riazanov and A. Voronkov. The design and implementation of Vampire. AI Communications, 15(2- 3):91-110, 2002.
  51. Riazanov and Voronkov, 2002b) A. Riazanov and A. Voronkov. Limited resource strategy in resolution theorem proving. Journal of Symbolic Computations, pages 1-14, 2002. to appear.
  52. Robinson and Wos, 1969) G. Robinson and L.T. Wos. Paramodu- lation and theorem-proving in first order theories with equality. In B. Meltzer and D. Michie, editors, Machine Intelligence, volume 4, pages 135-150. Edinburgh University Press, 1969.
  53. Robinson, 1965)
  54. J.A. Robinson. A machine-oriented logic based on the resolution principle. Journal of the Association for Computing Machinery, 12(1):23-41, 1965. Reprinted as [Robinson, 1983).
  55. Robinson, 1983)
  56. J.A. Robinson. A machine oriented logic based on the resolution principle. In J. Siekmann and G. Wrightson, edi- tors, Automation of Reasoning. Classical Papers on Computational Logic, volume 1, pages 397-415. Springer Verlag, 1983. Reprinted from (Robinson, 1965).
  57. RueB and Shankar, 2001)
  58. H. RueB and N. Shankar. Deconstructing Shostak. In L/CS 200I, pages 19-28, 2001.
  59. Schulz, 2001)
  60. S. Schulz. System abstract: E 0.61. In R. Gore, A. Leitsch, and T. Nipkow, editors, /JCAR 2001, volume 2083 of LNA1, pages 370-375. Springer Verlag, 2001.
  61. Schumann and Fischer, 1997) J. Schumann and B. Fischer. NORA/HAMMR: Making deduction-based software component retrieval practical. In Proc. Automated Software Engineering (ASE-97), pages 246--254. IEEE Computer Society Press, 1997.
  62. Sekar et at., 2001)
  63. R. Sekar, LV. Ramakrishnan, and A. Voronkov. Term indexing. In A. Robinson and A. Voronkov, editors, Handbook of Automated Reasoning, volume II, chapter 26, pages 1853-1964. Elsevier Science, 2001.
  64. Shostak, 1984)
  65. R.E. Shostak. Deciding combinations of theories. Journal of the Association for Computing Machinery, 31 (I): 1-12, 1984.
  66. Slaney et at., 1994)
  67. J.K. Slaney, E.L. Lusk, and W. McCune. SCOTT: Semantically Constrained Otter (system description). In A. Bundy, editor, CADE-12, volume 814 of LNAI, pages 764-768, 1994.
  68. Stickel et at., 1994)
  69. M. Stickel, R. Waldinger, R. Lowry, T. Press- burger, and I. Underwood. Deductive composition of astronomical software from subroutine libraries. In A. Bundy, editor, CADE-12 , volume 814 of LNA/, pages 341-355, 1994.
  70. Stickel et at., 2001)
  71. M.E. Stickel, R.J. Waldinger, and V.K. Chaudhri. A Guide to Snark. SRI, 2001. (Sutcliffe and Suttner, 1998) G. Sutcliffe and C. Suttner. The TPTP problem library -CNF release v. 1.2.1. Journal of Automated Rea- soning, 21(2), 1998.
  72. Sutcliffe et at., 2002)
  73. G. Sutcliffe, C.B. Suttner, and F. J. Pelletier. The IJCAR ATP system competition. Journal of Automated Rea- soning, 28(3):307-320, 2002.
  74. T. Tarnmet. Gandalf. Journal of Automated Reason- ing, 18(2): 199-204, 1997.
  75. The Coq Development Team, 2001) The Coq Development Team. The Coq Proof Assistant Reference Manual. Version 7.2. INRIA, 2001.
  76. Voronkov, 1995) A. Voronkov. The anatomy of Vampire: Imple- menting bottom-up procedures with code trees. Journal of Auto- mated Reasoning, 15(2):237-265, 1995.
  77. Weidenbach et at., 1996)
  78. C. Weidenbach, B. Gaede, and G. Rock. SPASS & FLOTTER. Version 0.42. In M.A. McRobbie and J.K. Slaney, editors, CADE-13, volume 1104 of LNCS, pages 141-145, 1996.
  79. Zhang and Malik, 2002) L. Zhang and S. Malik. The quest for effi- cient boolean satisfiability solvers. In A. Voronkov, editor, CADE- 18, volume 2392 of LNAI, pages 295-313, 2002.

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

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