We introduce a language, PSL, designed to capture high level proof strategies in Isabelle HOL. Given a strategy and a proof obligation, PSL's runtime system generates and combines various tactics to explore a large search space with low memory usage. Upon success, PSL generates an efficient proof script, which bypasses a large part of the proof search. We also present PSL's monadic interpreter to show that the underlying idea of PSL is transferable to other ITPs.
@cite_1 is an automated proof generation tool in Coq. Taking existing Coq theories as input, first produces proof traces, from which it infers an extended finite state machine. Given a conjecture, uses this model to search for its proof. 's search algorithm is based on the breadth-first search (BFS) to return the shortest proof. can also adopt BFS, as BFS is a special case of IDDFS. However, our experience tells that the search tree tends to be very wide and some tactics, such as , need to be followed by other tactics to complete proofs. Therefore, we chose IDDFS for . Both and off-load the construction of proof scripts to search and try to reconstruct efficient proof scripts. Compared to , allows users to specify their own search strategies to utilize the engineer's intuition, which enables to return incomplete proof scripts, as discussed in Section .
@cite_1
2071787143
Abstract In this paper, we outline a proof procedure which combines reasoning with defined predicates together with reasoning with undefined, abducible , predicates. Defined predicates are defined in if-and-only-if form. Abducible predicates are constrained by means of integrity constraints. Given an initial query, the task of the proof procedure is to construct a definition of the abducible predicates and a substitution for the variables in the query, such that both the resulting instance of the query and the integrity constraints are implied by the extended set of definitions. The iff proof procedure can be regarded as a hybrid of the proof procedure of and the SLDNFA procedure of Denecker and De Schreye. It consists of a number of inference rules which, starting from the initial query, rewrite a formula into an equivalent formula. These rules are: 1) unfolding , which replaces an atom by its definition; 2) propagation , which resolves an atom with an implication; 3) splitting , which uses distributivity to represent a goal as a disjunction of conjunctions; 4) case analysis for an equality X = t in the conditions of an implication, which considers the two cases X = t and X ≠ t ; 5) factoring of two abducible atoms, which considers the two cases, where the atoms are identical and where they are different, 6) rewrite rules for equality , which simulate the unification algorithm; and 7) logical simplifications , such as A ∧ false ↔ false . The proof procedure is both sound and complete relative to the three-valued completion semantics. These soundness and completeness results improve previous results obtained for other proof procedures.