Hierarchical invention of theorem proving strategies

Issue title: Automated Reasoning

Guest editors: Pascal Fontaine, Cezary Kaliszyk, Stephan Schulz and Josef Urban

Article type: Research Article

Authors: Jakubův, Jan^{; *} | Urban, Josef

Affiliations: CIIRC, Czech Technical University in Prague, Czech Republic. E-mails: jakubuv@gmail.com, josef.urban@gmail.com

Correspondence: [*] Corresponding author. E-mail: jakubuv@gmail.com.

Abstract: State-of-the-art automated theorem provers (ATPs) such as E and Vampire use a large number of different strategies to traverse the search space. Inventing targeted proof search strategies for specific problem sets is a difficult task. Several machine learning methods that invent strategies automatically for ATPs have been proposed previously. One of them is the Blind Strategymaker (BliStr) system for inventing strategies of the E prover. In this paper we describe BliStrTune – a hierarchical extension of BliStr. BliStrTune explores much larger space of E strategies than BliStr by interleaving search for high-level parameters with their fine-tuning. We use BliStrTune to invent new strategies based also on new clause weight functions targeted at problems from large ITP libraries. We show that the new strategies significantly improve E’s performance.

Keywords: Automated theorem proving, parameter learning, proof search heuristics, clause weight functions

DOI: 10.3233/AIC-180761

Journal: AI Communications, vol. 31, no. 3, pp. 237-250, 2018