Abstract
This paper advocates and explores the use of multi-predicate induction schemes for proofs about mutually recursive functions. The interactive application of multi-predicate schemes stemming from datatype definitions is already well-established practice; this paper describes an automated proof procedure based on multi-predicate schemes. Multi-predicate schemes may be formally derived from (mutually recursive) function definitions; such schemes are often helpful in proving properties of mutually recursive functions where the recursion pattern does not follow that of the underlying datatypes. These ideas have been implemented using the HOL theorem prover and the Clam proof planner.
Research supported by the Engineering and Physical Sciences Research Council of Great Britain under grants GR/L03071 and GR/L14381. The authors thank Alan Bundy, Ian Green and Christoph Walther for their feedback on this work.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. Boulton, K. Slind, A. Bundy, and M. Gordon. An interface between CLAM and HOL. In Proceedings of the 11th International Conference on Theorem Proving in Higher Order Logics (TPHOLs’ 98), volume 1479 of Lecture Notes in Computer Science, pages 87–104, Springer, 1998.
R. J. Boulton. Multi-predicate induction schemes for mutual recursion. Informatics Research Report EDI-INF-RR-0014, Division of Informatics, University of Edinburgh, April 2000.
R. S. Boyer and J S. Moore. A Computational Logic. ACM Monograph Series. Academic Press, New York, 1979.
A. Bundy, A. Stevens, F. van Harmelen, A. Ireland, and A. Smaill. Rippling: A heuristic for guiding inductive proofs. Artificial Intelligence, 62:185–253, 1993.
A. Bundy, F. van Harmelen, C. Horn, and A. Smaill. The OYSTER-CLAM system. In Proceedings of the 10th International Conference on Automated Deduction, volume 449 of Lecture Notes in Artificial Intelligence, pages 647–648, Springer, 1990.
M. J. C. Gordon and T. F. Melham, editors. Introduction to HOL: A theorem proving environment for higher order logic. Cambridge University Press, 1993.
J. T. Hesketh. Using Middle-Out Reasoning to Guide Inductive Theorem Proving. PhD thesis, University of Edinburgh, 1991.
D. Kapur and M. Subramaniam. Automating induction over mutually recursive functions. In Proceedings of the 5th International Conference on Algebraic Methodology and Software Technology (AMAST’96), volume 1101 of Lecture Notes in Computer Science, Springer, 1996.
P. Liu and R.-J. Chang. A new structural induction scheme for proving properties of mutually recursive concepts. In Proceedings of the 6th National Conference on Artificial Intelligence, volume 1, pages 144–148. AAAI, July 1987.
L. C. Paulson. ML for the Working Programmer. Cambridge University Press, 2nd edition, July 1996.
M. Protzen. Lazy generation of induction hypotheses. In Proceedings of the 12th International Conference on Automated Deduction (CADE-12), volume 814 of Lecture Notes in Artificial Intelligence, pages 42–56, Springer, 1994.
K. Slind. Function definition in higher-order logic. In Proceedings of the 9th International Conference on Theorem Proving in Higher Order Logics (TPHOLs’96), volume 1125 of Lecture Notes in Computer Science, pages 381–397, Springer, 1996.
K. Slind. Derivation and use of induction schemes in higher-order logic. In Proceedings of the 10th International Conference on Theorem Proving in Higher Order Logics (TPHOLs’97), volume 1275 of Lecture Notes in Computer Science, pages 275–290, Springer, 1997.
K. Slind. Reasoning about Terminating Functional Programs. PhD Thesis, Institut für Informatik, Technische Universität München, 1999. Accessible at http://www.cl.cam.ac.uk/users/kxs/papers.
M. VanInwegen and E. Gunter. HOL-ML. In Proceedings of the 6th International Workshop on Higher Order Logic Theorem Proving and its Applications (HUG’93), volume 780 of Lecture Notes in Computer Science, pages 61–74, Springer, 1994.
C. Walther. Combining induction axioms by machine. In Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence (IJCAI-93), volume 1, pages 95–100, Morgan Kaufmann Publishers, Inc.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boulton, R.J., Slind, K. (2000). Automatic Derivation and Application of Induction Schemes for Mutually Recursive Functions. In: Lloyd, J., et al. Computational Logic — CL 2000. CL 2000. Lecture Notes in Computer Science(), vol 1861. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44957-4_42
Download citation
DOI: https://doi.org/10.1007/3-540-44957-4_42
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67797-0
Online ISBN: 978-3-540-44957-7
eBook Packages: Springer Book Archive