Abstract
One of the many abilities that distinguish a mathematician from an automated deduction system is to be able to offer appropriate expressions based on intuition and experience that are substituted for existentially quantified variables so as to simplify the problem at hand substantially. We propose to simulate this ability with a technique called genetic programming for use in automated deduction. We apply this approach to problems of combinatory logic. Our experimental results show that the approach is viable and actually produces very promising results. A comparison with the renowned theorem prover Otter underlines the achievements.
This work was supported by the Deutsche Forschungsgemeinschaft (DFG).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barendregt, H.P.:The Lambda Calculus: Its Syntax and Semantics, North-Holland, Amsterdam, 1981.
Biundo, S.:Automated Synthesis of Recursive Algorithms as a Theorem Proving Tool, Proc. 8th European Conference on AI (ECAI-88), Munich, GER, 1988, Pitman Publishing, pp. 553–558.
Curry, H.B.; Feys, R.:Combinatory Logic, North-Holland, Amsterdam, 1958.
Denzinger, J.; Fuchs, M.:Goal oriented equational theorem proving using teamwork, Proc. 18th German Conference on AI (KI-94), Saarbrücken, GER, 1994, Springer LNAI 861, pp. 343–354.
De Jong, K.:Learning with Genetic Algorithms: An Overview, Machine Learning 3:121–138, 1988.
Dracopoulos, D.C.; Kent, S.:Speeding up Genetic Programming: A Parallel BSP Implementation, Proc. 1st International Conference on Genetic Programming (GP-96), Stanford University, CA, USA, 1996, MIT Press, p. 421.
Ertel, W.:Random Competition: A Simple, but Efficient Method for Parallelizing Inference Systems, Techn. Report TUM-19050, Technical University of Munich, 1990.
Holland, J.H.:Adaptation in natural and artificial systems, Ann Arbor: Univ. of Michigan Press, 2nd edition, 1992.
Koza, J.R.:Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press, Cambridge, MA, 1992.
Koza, J.R.:Genetic Programming II: Automatic Discovery of Reusable Programs, MIT Press, Cambridge, MA, 1994.
Lusk, E.; McCune, W.:Uniform Strategies: The CADE-11 Theorem Proving Contest, Journal of Automated Reasoning 11:317–331, 1993.
Lusk, E.; Wos, L.:Benchmark Problems in Which Equality Plays the Major Role, CADE-11, Saratoga Springs, NY, USA, 1992, Springer LNAI 607, pp. 781–785.
McCune, W.:OTTER 3.0 Reference Manual and Guide, Techn. Report ANL-94/6, Argonne Natl. Laboratory, 1994.
McCune, W.; Wos, L.:A Case Study in Automated Theorem Proving: Finding Sages in Combinatory Logic, Journal of Automated Reasoning 3:91–107, 1987.
Niwa, T.; Iba, H.:Distributed Genetic Programming: Empirical Study and Analysis, Proc. 1st International Conference on Genetic Programming (GP-96), Stanford University, CA, USA, 1996, MIT Press, pp. 339–344.
O'Donnell, M.J.:Computing in Systems Described by Equations, Springer LNCS 58, 1977.
Smullyan, R.:To Mock a Mockingbird, A. Knopf, New York, 1985.
Sutcliffe, G.; Suttner, C.; Yemenis, T.:The TPTP Problem Library, Proc. CADE-12, Nancy, FRA, 1994, Springer LNAI 814, pp. 252–266.
Wos, L.; McCune, W.:Challenge Problems Focusing on Equality and Combinatory Logic: Evaluating Automated Theorem-Proving Programs, CADE-9, Argonne, IL, USA, 1988, Springer LNCS 310, pp. 714–729.
Wos, L.; Winker, S.; McCune, W.; Overbeek, R., Lusk, E.; Stevens, R.:Automated Reasoning Contributes to Mathematics and Logic, CADE-10, Kaiserslautern, GER, 1990, Springer LNAI 449, pp. 485–499.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fuchs, M. (1997). Evolving combinators. In: McCune, W. (eds) Automated Deduction—CADE-14. CADE 1997. Lecture Notes in Computer Science, vol 1249. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63104-6_42
Download citation
DOI: https://doi.org/10.1007/3-540-63104-6_42
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63104-0
Online ISBN: 978-3-540-69140-2
eBook Packages: Springer Book Archive