Autarkic Computations in Formal Proofs

Formal proofs in mathematics and computer science are being studied because these objects can be verified by a very simple computer program. An important open problem is whether these formal proofs can be generated with an effort not much greater than writing a mathematical paper in, say, LATEX. Modern systems for proof development make the formalization of reasoning relatively easy. However, formalizing computations in such a manner that the results can be used in formal proofs is not immediate. In this paper we show how to obtain formal proofs of statements such as Prime(61) in the context of Peano arithmetic or (x+1)(x+1)=x ²+2x+1 in the context of rings. We hope that the method will help bridge the gap between the efficient systems of computer algebra and the reliable systems of proof development.     

Proving Ramsey's theorem by the cover set induction: A case and comparison study

An experiment of the cover set induction method inRRL is presented with a mechanical proof of Ramsey's theorem in graph theory. The proof is similar to the proof obtained by Kaufmann using the Boyer-Moore theorem prover. We show that this similarity is not unusual, because there is a close relationship between the Boyer-Moore logic and the algebraic specification of abstract data types on which the cover set induction method is based. (This implies that many proofs done by the Boyer-Moore theorem prover can be reproduced byRRL.) Our experiment shows thatRRL can automatically prove all the lemmas in Ramsey's theorem, while the Boyer-Moore theorem prover needs several user's hints and takes much longer (CPU time) to finish.Partially supported by National Science Foundation Grants Nos. CCR-9202838 and INT-9016100.     

Automated production of traditional proofs for theorems in Euclidean geometry I. The Hilbert intersection point theorems

We present a method which can produce traditional proofs for a class of constructive geometry statements in Euclidean geometry. The method is a mechanization of the traditional area method used by many geometers. The key idea of our method is to eliminate dependent (constructed) points in a geometry statement using a few basic geometry propositions about the area of triangles. The method has been implemented. Our program, calledEuclid, can produce traditional proofs of many hard geometry theorems such as Pappus' theorem, Pascal's theorem, Gauss point theorem, and the Pascal conic theorem. Currently, it has produced proofs of 110 nontrivial theoremsentirely automatically. The proofs produced byEuclid are elegant, short (often shorter than the proofs given by geometers) and understandable even to high school students. This method seems to be the first that can produce traditional proofs for hard geometry theorems automatically.The work reported here was supported in part by the NSF Grant CCR-9117870 and the Chinese National Science Foundation.On leave from the Institute of Systems Sciences, Academia Sinica, Beijing 100080, P.R. China.     

The rue theorem-proving system: The complete set of LIM+ challenge problems

In this paper we discuss the successful execution of the LIM+ challenge problems as proposed by Bledsoe. This problem set ranges from a 12-step nonequality proof to a complex 41-step paramodulation proof. Our theorem prover is based on RUE resolution, which incorporates the axioms of equality into the definition of resolution. We apply hyperresolution as a restriction strategy and produce RUE hyper-refutations without the use of paramodulation. We present an extensive treatment of the heuristics applied to find proofs, both standalone and interactive.This work was supported by the National Science Foundation Grant CCR-9024953.     

Integrating Computer Algebra into Proof Planning

Mechanized reasoning systems and computer algebra systems have different objectives. Their integration is highly desirable, since formal proofs often involve both of the two different tasks proving and calculating. Even more important, proof and computation are often interwoven and not easily separable.In this article we advocate an integration of computer algebra into mechanized reasoning systems at the proof plan level. This approach allows us to view the computer algebra algorithms as methods, that is, declarative representations of the problem-solving knowledge specific to a certain mathematical domain. Automation can be achieved in many cases by searching for a hierarchic proof plan at the method level by using suitable domain-specific control knowledge about the mathematical algorithms. In other words, the uniform framework of proof planning allows us to solve a large class of problems that are not automatically solvable by separate systems.Our approach also gives an answer to the correctness problems inherent in such an integration. We advocate an approach where the computer algebra system produces high-level protocol information that can be processed by an interface to derive proof plans. Such a proof plan in turn can be expanded to proofs at different levels of abstraction, so the approach is well suited for producing a high-level verbalized explication as well as for a low-level, machine-checkable, calculus-level proof.We present an implementation of our ideas and exemplify them using an automatically solved example.Changes in the criterion of rigor of the proof' engender major revolutions in mathematics. H. Poincaré, 1905     

Local proofs for global safety properties

This paper explores locality in proofs of global safety properties of concurrent programs. Model checking on the full state space is often infeasible due to state explosion. A local proof, in contrast, is a collection of per-process invariants, which together imply the desired global safety property. Local proofs can be more compact than global proofs, but local reasoning is also inherently incomplete. In this paper, we present an algorithm for safety verification that combines local reasoning with gradual refinement. The algorithm gradually exposes facts about the internal state of components, until either a local proof or a real error is discovered. The refinement mechanism ensures completeness. Experiments show that local reasoning can have significantly better performance over the traditional reachability computation. Moreover, for some parameterized protocols, a local proof can be used as the basis of a correctness proof over all instances.     

Searching for circles of pure proofs

When given a set of properties or conditions (say, three) that are claimed to be equivalent, the claim can be verified by supplying what we call acircle of proofs. In the case in point, one proves the second property or condition from the first, the third from the second, and the first from the third. If the proof that 1 implies 2 does not rely on 3, then we say that the proof is pure with respect to 3, or simply say theproof is pure. If one can renumber the three properties or conditions in such a way that one can find a circle of three pure proofs — technically, each proof pure with respect to the condition that is neither the hypothesis nor the conclusion — then we say that acircle of pure proofs has been found. Here we study the specific question of the existence of a circle of pure proofs for the thirteen shortest single axioms for equivalential calculus, subject to the requirement that condensed detachment be used as the rule of inference. For an indication of the difficulty of answering the question, we note that a single application of condensed detachment to the (shortest single) axiom known asP4 (also known asUM) with itself yields the (shortest single) axiomP5 (also known asXGF), and two applications of condensed detachment beginning withP5 as hypothesis yieldsP4. Therefore, except forP5, one cannot find a pure proof of any of the twelve shortest single axioms when usingP4 as hypothesis or axiom, for the first application of condensed detachment must focus on two copies ofP4, which results in the deduction ofP5, forcingP5 to be present in all proofs that useP4 as the only axiom. Further, the close proximity in the proof sense ofP4 when using as the only axiomP5 threatens to make impossible the discovery of a circle of pure proofs for the entire set of thirteen shortest single axioms. Perhaps more important than our study of pure proofs, and of a more general nature, we also present the methodology used to answer the cited specific question, a methodology that relies on various strategies and features offered by W. McCune's automated reasoning programOtter. The strategies and features ofOtter we discuss here offer researchers the needed power to answer deep questions and solve difficult problems. We close this article (in the last two sections) with some challenges and some topics for research and (in the Appendix) with a sample input file and some proofs for study.Author supported by the Mathematical, Information, and Computational Sciences Division, Subprogram of the Office of Computational and Technology Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Formal proof of integer adders using all-prefix-sums operation

Addition of two binary numbers is a fundamental operation in electronic circuits.Several integer adder architectures have been proposed.Their formal properties are well known,but the proofs are either incomplete or difficult to find.In this paper,we present a formal proof for the correctness of prefix adders.Both sequential and parallel algorithms are formalized and proved.In contrast to previous proofs using higher order functions and rewriting systems,our work is based on first order recursive equations,which are familiar to the computer arithmetic community and are therefore understandable by people working on VLSI circuit design.This study sets up a basis for further work on formal proofs of computer arithmetic algorithms.     

Comparing Approaches to the Exploration of the Domain of Residue Classes

We report on a case study on combining proof planning with computer algebra systems. We construct proofs for basic algebraic properties of residue classes as well as for isomorphisms between residue classes using different proof techniques, which are implemented as strategies in a multi-strategy proof planner. The search space of the proof planner can be drastically reduced by employing computations of two computer algebra systems during the planning process. To test the effectiveness of our approach we carried out a large number of experiments and also compared it with some alternative approaches. In particular, we experimented with substituting computer algebra by model generation and by proving theorems with a first-order equational theorem prover instead of a proof planner.     

Randomized competitive algorithms for the list update problem

We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is more competitive than the best previous randomized algorithm due to Irani. Our algorithm uses randomness only during an initialization phase, and from then on runs completely deterministically. It is the first randomized competitive algorithm with this property to beat the deterministic lower bound. We generalize our approach to a model in which access costs are fixed but update costs are scaled by an arbitrary constantd. We prove lower bounds for deterministic list update algorithms and for randomized algorithms against oblivious and adaptive on-line adversaries. In particular, we show that for this problem adaptive on-line and adaptive off-line adversaries are equally powerful.A preliminary version of these results appeared in a joint paper with S. Irani in theProceedings of the 2nd Symposium on Discrete Algorithms, 1991 [17].This research was partially supported by NSF Grants CCR-8808949 and CCR-8958528.This research was partially supported by NSF Grant CCR-9009753.This research was supported in part by the National Science Foundation under Grant CCR-8658139, by DIMACS, a National Science Foundation Science and Technology center, Grant No. NSF-STC88-09648.     

Reducing the size of resolution proofs in linear time

DPLL-based SAT solvers progress by implicitly applying binary resolution. The resolution proofs that they generate are used, after the SAT solver’s run has terminated, for various purposes. Most notable uses in formal verification are: extracting an unsatisfiable core, extracting an interpolant, and detecting clauses that can be reused in an incremental satisfiability setting (the latter uses the proof only implicitly, during the run of the SAT solver). Making the resolution proof smaller can benefit all of these goals: it can lead to smaller cores, smaller interpolants, and smaller clauses that are propagated to the next SAT instance in an incremental setting. We suggest two methods that are linear in the size of the proof for doing so. Our first technique, called Recycle-Units uses each learned constant (unit clause) (x) for simplifying resolution steps in which x was the pivot, prior to when it was learned. Our second technique, called   simplifies proofs in which there are several nodes in the resolution graph, one of which dominates the others, that correspond to the same pivot. Our experiments with industrial instances show that these simplifications reduce the core by ≈5% and the proof by ≈13%. It reduces the core less than competing methods such as run- till- fix, but whereas our algorithms are linear in the size of the proof, the latter and other competing techniques are all exponential as they are based on SAT runs. If we consider the size of the proof (the resolution graph) as being polynomial in the number of variables (it is not necessarily the case in general), this gives our method an exponential time reduction comparing to existing tools for small core extraction. Our experiments show that this result is evident in practice more so for the second method: rarely it takes more than a few seconds, even when competing tools time out, and hence it can be used as a cheap proof post-processing procedure.     

A framework for counterexample generation and exploration

Model-checking is becoming an accepted technique for debugging hardware and software systems. Debugging is based on the “Check/Analyze/Fix” loop: check the system against a desired property, producing a counterexample when the property fails to hold; analyze the generated counterexample to locate the source of the error; fix the flawed artifact—the property or the model. The success of model-checking non-trivial systems critically depends on making this Check/Analyze/Fix loop as tight as possible. In this paper, we concentrate on the Analyze part of the debugging loop. To this end, we present a framework for generating, structuring and exploring counterexamples, implemented in a tool called KEGVis. The framework is based on the idea that the most general type of evidence to why a property holds or fails to hold is a proof. Such proofs can be presented to the user in the form of proof-like counterexamples, without sacrificing any of the intuitiveness and close relation to the model that users have learned to expect from model-checkers. Moreover, proof generation is flexible, and can be controlled by strategies, whether built into the tool or specified by the user, thus enabling generation of the most “interesting” counterexample and its interactive exploration. Moreover, proofs can be used to generate and display all relevant evidence together, a technique referred to as abstract counterexamples. Overall, our framework can be used for explaining the reason why the property failed or succeeded, determining whether the property was correct (“specification debugging”), and for general model exploration.     

Exponential lower bounds for the pigeonhole principle

In this paper we prove an exponential lower bound on the size of bounded-depth Frege proofs for the pigeonhole principle (PHP). We also obtain an (loglogn)-depth lower bound for any polynomial-sized Frege proof of the pigeonhole principle. Our theorem nearly completes the search for the exact complexity of the PHP, as S. Buss has constructed polynomial-size, logn-depth Frege proofs for the PHP. The main lemma in our proof can be viewed as a general Håstad-style Switching Lemma for restrictions that are partial matchings. Our lower bounds for the pigeonhole principle improve on previous superpolynomial lower bounds.     

Automated deduction in von Neumann-Bernays-Gödel set theory

I present a new clausal version of NGB set theory, and compare my version with that first given by Boyer et al. [4]. A complete set of reductions for Boolean rings is given, derived from those of Hsiang [7]. I list over 400 theorems proved semiautomatically in elementary set theory, and supply the proofs of several of these, including Cantor's theorem. I present a semiautomated proof that the composition of homomorphisms is a homomorphism, thus solving a challenge problem given in [4]. Using the clauses and heuristics presented, there is no apparent obstacle to the semiautomated development of set theory through considerably more difficult theorems.     

Lower bounds for the polynomial calculus

We show that polynomial calculus proofs (sometimes also called Groebner proofs) of the pigeonhole principle must have degree at least over any field. This is the first non-trivial lower bound on the degree of polynomial calculus proofs obtained without using unproved complexity assumptions. We also show that for some modifications of , expressible by polynomials of at most logarithmic degree, our bound can be improved to linear in the number of variables. Finally, we show that for any Boolean function in n variables, every polynomial calculus proof of the statement “ cannot be computed by any circuit of size t,” must have degree . Loosely speaking, this means that low degree polynomial calculus proofs do not prove . Received: January 15, 1997.     

A note on an identity-based ring signature scheme with signer verifiability

Recently, Herranz presented an identity-based ring signature scheme featuring signer verifiability where a signer can prove that he or she is the real signer by releasing an authorship proof. In this paper we show that this scheme is vulnerable to a key recovery attack in which a user’s secret signing key can be efficiently recovered through the use of two known ring signatures and their corresponding authorship proofs. In addition, we present a simple method to fix this security vulnerability by slightly modifying the authorship proof. Our modified scheme simplifies the original scheme and improves performance. To show that the modified scheme is unforgeable, we define two types of unforgeability notions for both signatures and authorship proofs. In these notions an adversary has opening capability to confirm the real signers of ring signatures and thus can manipulate authorship proofs in an adaptive way. We then prove that our modified scheme is secure in terms of these unforgeability notions.     

HANDLING INFORMATION LOGICS IN A GRAPHICAL PROOF EDITOR

In order to provide a background for rough set modeling of uncertainty, two types of incompleteness of information are discussed. Representation of uncertain knowledge acquired from incomplete information is outlined within the framework of information logics. Relational proof theory for the information logics is presented. It is shown how these logics and their proof systems can be handled in the GLEFATINF (Graphical & Logical Editing Framework) system. This computer program is a key component of the inference laboratory Atelier d'Inféence (ATINF) developed at LIFIA-IMAG, our lab. It provides a general framework, independent of logic and proof systems, for combining inference tools, editing, and checking proofs. The basic principles of its design and implementation are given and its capabilities are discussed. Its application to define the information logics and their proof systems and to present proofs in these proof systems is discussed and illustrated.     

Automated generation of readable proofs with geometric invariants

We present a set of rules based on full-angles as the basis of automated geometry theorem proving. We extend the idea of eliminating variables and points to the idea of eliminating lines. We also discuss how to combine the forward chaining and backward chaining to achieve higher efficiency. The prover based on the full-angle method has been used to produce short and elegant proofs for more than one hundred difficult geometry theorems. The proofs of many of those theorems produced by our previous area method are relatively long.This work was supported in part by the NSF Grants CCR-9117870, CCR-9420857 and the Chinese NSF.     

OTTER and the Moufang identity problem

This article provides additional evidence of the value of using an automated reasoning program as a research assistant. Featured is the use of Bill McCune's program OTTER to find proofs of theorems taken from the study of Moufang loops, but not just any proofs. Specifically, the proofs satisfy the property of purity. In particular, when given, say, four equivalent identities (which is the case in this article), one is asked to prove the second identity from the first, the third from the second, the fourth from the third, and the first from the fourth. If the proof that 1 implies 2 does not rely on 3 or 4, then by definition the proof is pure with respect to 3 and 4, or simply the proof is pure. If for the four identities one finds four pure proofs showing that 1 implies 2, 2 implies 3, 3 implies 4, and 4 implies 1, then by definition one has found a circle of pure proofs. By finding the needed twelve pure proofs, this article shows that there does exist a circle of pure proofs for the four equivalent identities for Moufang loops and for all orderings of the identities; however, for much of this article, the emphasis is on the first three identities. In addition — in part to promote the use of automated reasoning programs and to answer questions concerning the choice of options — featured here is the methodology that was employed and a discussion of some of the obstacles, some of which are subtle. The approach relies on paramodulation (which generalizes equality substitution), on demodulation, and — so crucial for attacking deep questions and hard problems — on various strategies, most important of which are the hot list strategy, the set of support strategy, and McCune's ratio strategy. To permit verification of the results presented here, extension of them, and application of the methodology to other unrelated fields, a sample input file and four proofs (relevant to a circle of pure proofs for the four identities) are included. Research topics and challenges are offered at the close of this article.This work was supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Computational and Technology Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.