Proceedings

Automatic Case Analysis in Proof by Induction

Download BibTeX Cite

Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 88-93.

© 1993 International Joint Conferences on Artificial Intelligence

Abstract

We propose a new procedure for proof by induction in conditional theories where case analysis is simulated by term rewriting. This technique reduces considerably the number of variables of a conjecture to be considered for applying induction schemes (inductive positions). Our procedure is presented as a set of inference rules whose correctness has been formally proved. Moreover, when the axioms are ground convergent and the defined functions are completely defined over free constructors, it is possible to apply the system for refuting conjectures. The procedure is even refutationally complete for conditional equations with boolean preconditions (under the same hypotheses). The method is entirely implemented in the prover SPIKE . This system has proved interesting examples in a completely automatic way, that is, without interaction with the user and without ad-hoc heuristics. It has also proved the challenging Gilbreath card trick, with only, 5 easy lemmas.

  1. [Bevers, 1993] E. Bevers. Automated Reasonning in Condi- tional Algebric Specifications: Termination and Proof by Consistency. PhD thesis, Katholieke Universiteit Leuven, Belgium, 1993.
  2. [Bouhoula et al., 1992a] A. Bouhoula, E. Kounalis, and M. Rusinowitch . Automated mathematical induction. Technical Report 1636, INRIA, 1992.
  3. [Bouhoula et al., 1992b] A. Bouhoula, E. Kounalis, and M. Rusinowitch. Spike: an automatic theorem prover. In Proceedings of LPAR '92, volume 624 of LNAI, Saint Pe- ters bourg, Russia, July 1992. Springer-Verlag.
  4. [Boyer and Moore, 1979] R. S. Boyer and J. S. Moore. A Computational Logic. Academic Press, New York, 1979.
  5. [Bronsard and Reddy, 1990] F. Bronsard and S. Reddy. Con- ditional rewriting in focus. InS. Kaplan and M. Okada, ed- itors, Proceedings of the 2nd Workshop on Conditional and Typed Rewriting Systems, volume 516 of LNCS. Springer- Verlag, 1990.
  6. [Bundy et al., 1989] A. Bundy, F. van Harmelen, A. Smaill, and A. Ireland. Extensions to the rippling-out tactic for guiding inductive proofs. In M. E. Stickel, editor, 10th In- ternational Conference on Automated Deduction, volume 449 of LNAI, pages 132-146. Springer-Verlag, July 1989.
  7. [Chadha and Plaisted, 1992] R. Chadha and D.A. Plaisted. Mechanizing mathematical induction. Presented at the 94 Automated Reasoning Second International Symposium on Artificial Intelligence and Mathematics, Fort Lauderdale, Florida, 1992.
  8. [Dershowitz and Jouannaud, 1990] N. Dershowitz and J .-P. Jouannaud. Rewrite systems. In J. van Leuven, editor, Handbook of Theoretical Computer Science. Elsevier Sci- ence Publishers North-Holland, 1990.
  9. [Dershowitz et al., 1988] N. Dershowitz, M. Okada, and G. Sivakumar. Canonical conditional rewrite systems. In Proceedings 9th International Conference on Automated Deduction, Argonne {fll., USA}, volume 310 of LNCS. Springer-Verlag, May 1988.
  10. L. Fribourg. A strong restriction of the in- ductive completion procedure. In Proceedings 13th Inter- national Colloquium on Automata, Languages and Pro- gramming, volume 226 of LNCS, pages 105-115. Springer- Verlag, 1986.
  11. [Huber, 1991] M. Huber. Test-set approaches for ground re- ducibility in term rewriting systems, characterizations and new applications. Master's thesis, Technische Universitii.t Berlin, 1991.
  12. [Huet and Hullot, 1982] G. Huet and J.-M. Hullot. Proofs by induction in equational theories with constructors. Journal of Computer and System Sciences, 25(2) :239-266, October 1982.
  13. [Huet, 1991] G. Huet. The Gilbreath trick: a case study in axiomatisation and proof development in the coq proof assistant. Technical Report 1511, INRIA, 1991.
  14. [Jouannaud and Kounalis, 1986] J.-P. Jouannaud and E. Kounalis. Proof by induction in equational theories with- out constructors. In Proceedings 1st IEEE Symposium on Logic in Computer Science, Cambridge (Mass., USA), pages 358-366, 1986.
  15. [Kounalis and Rusinowitch, 1990a] E. Kounalis and M. Ru- sinowitch. A mechanization of conditional reasoning. In First International Symposium on Artificial Intelligen ce and Mathematics, Fort Lauderdale, Florida, January 1990.
  16. [Kounalis and Rusinowitch, 1990b] E. Kounalis and M. Ru- sinowitch. Mechanizing inductive reasoning. In Proceed- ings of the American Association for Artificial Intelligen ce Conference, Boston, pages 240-245. AAAI Press and MIT Press, July 1990.
  17. [Kounalis, 1990] E. Kounalis. Testing for inductive (co)- reducibility. In A. Arnold, editor, Proceedings 15th CAAP, Copenhagen (Denmark}, volume 431 of LNCS, pages 221- 238. Springer-Verlag, May 1990.
  18. [Musser, 1980] D. R. Musser. On proving inductive proper- ties of abstract data types. In Proceedings 7th ACM Symp . on Principles of Programming Languages, pages 154-162. Association for Computing Machinery, 1980.
  19. [Reddy, 1990] U. S. Reddy. Term rewriting induction. In M. E. Stickel, editor, Proceedings 10th International Con- ference on Automated Deduction, Kaiserslautern {Ger- many), volume 449 of LNCS, pages 162-177. Springer- Verlag, 1990.
  20. [Zhang et al., 1988] H. Zhang, D. Kapur, and M. S. Krish- namoorthy. A mechanizable induction principle for equa- tional specifications. In E. Lusk and R. Overbeek, editors, Proceedings 9th International Conference on Automated Deduction, Argonne {fll., USA}, volume 310 of LNCS, pages 162-181. Springer-Verlag, 1988.
  21. [Zhang, 1993] H. Zhang Implementing Contextual Rewriting Proceedings of the 9rd CTRS Workshop, volume 656 of LNCS. Springer-Verlag, 1993.

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

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