Journal of Automated Reasoning

This article describes the development and formal verification (proof of semantic preservation) of a compiler back-end from Cminor (a simple imperative intermediate language) to PowerPC assembly code, using the Coq proof assistant both for programming the compiler and for proving its soundness. Such a verified compiler is useful in the context of formal methods applied to the certification of critical software: the verification of the compiler guarantees that the safety properties proved on the source code hold for the executable compiled code as well.

This paper improves the treatment of equality in guarded dependent type theory ( $$\mathsf {GDTT}$$ ), by combining it with cubical type theory ( $$\mathsf {CTT}$$ ). $$\mathsf {GDTT}$$ is an extensional type theory with guarded recursive types, which are useful for building models of program logics, and for programming and reasoning with coinductive types. We wish to implement $$\mathsf {GDTT}$$ with decidable type checking, while still supporting non-trivial equality proofs that reason about the extensions of guarded recursive constructions. $$\mathsf {CTT}$$ is a variation of Martin–Löf type theory in which the identity type is replaced by abstract paths between terms. $$\mathsf {CTT}$$ provides a computational interpretation of functional extensionality, enjoys canonicity for the natural numbers type, and is conjectured to support decidable type-checking. Our new type theory, guarded cubical type theory ( $$\mathsf {GCTT}$$ ), provides a computational interpretation of extensionality for guarded recursive types. This further expands the foundations of $$\mathsf {CTT}$$ as a basis for formalisation in mathematics and computer science. We present examples to demonstrate the expressivity of our type theory, all of which have been checked using a prototype type-checker implementation. We show that $$\mathsf {CTT}$$ can be given semantics in presheaves on $$\mathcal {C}\times \mathbb {D}$$ , where $$\mathcal {C}$$ is the cube category, and $$\mathbb {D}$$ is any small category with an initial object. We then show that the category of presheaves on $$\mathcal {C}\times \omega $$ provides semantics for $$\mathsf {GCTT}$$ .

The Akra–Bazzi method (Akra and Bazzi in Comput Optim Appl 10(2):195–210, 1998. doi: 10.1023/A:1018373005182 ), a generalisation of the well-known Master Theorem, is a useful tool for analysing the complexity of Divide and Conquer algorithms. This work describes a formalisation of the Akra–Bazzi method (as generalised by Leighton in Notes on better Master theorems for divide-and-conquer recurrences, 1996. http://courses.csail.mit.edu/6.046/spring04/handouts/akrabazzi.pdf ) in the interactive theorem prover Isabelle/HOL and the derivation of a generalised version of the Master Theorem from it. We also provide some automated proof methods that facilitate the application of this Master Theorem and allow mostly automatic verification of $$\varTheta $$ -bounds for these Divide and Conquer recurrences. To our knowledge, this is the first formalisation of theorems for the analysis of such recurrences.

Resolution proof systems for quantified Boolean formulas (QBFs) provide a formal model for studying the limitations of state-of-the-art search-based QBF solvers that use these systems to generate proofs. We study a combination of two proof systems supported by the solver DepQBF: Q-resolution with generalized universal reduction according to a dependency scheme and long distance Q-resolution. We show that the resulting proof system—which we call long-distance Q(D)-resolution—is sound for the reflexive resolution-path dependency scheme. In fact, we prove that it admits strategy extraction in polynomial time. This comes as an application of a general result, by which we identify a whole class of dependency schemes for which long-distance Q(D)-resolution admits polynomial-time strategy extraction. As a special case, we obtain soundness and polynomial-time strategy extraction for long distance Q(D)-resolution with the standard dependency scheme. We further show that search-based QBF solvers using a dependency scheme D and learning with long-distance Q-resolution generate long-distance Q(D)-resolution proofs. The above soundness results thus translate to partial soundness results for such solvers: they declare an input QBF to be false only if it is indeed false. Finally, we report on experiments with a configuration of DepQBF that uses the standard dependency scheme and learning based on long-distance Q-resolution.

In this paper a new method is proposed for mechanically proving theorems in the local theory of space curves. The method is based on Ritt-Wu’s well-ordering principle of ordinary differential polynomials, Clifford algebraic representation of Euclidean space and equation set solving in Clifford algebra formalism. It has been tested by various theorems and seems to be efficient.

This paper reports on the MIZAR formalization of the theory of continuous lattices as presented in Gierz et al.: A Compendium of Continuous Lattices, 1980. By a MIZAR formalization we mean a formulation of theorems, definitions, and proofs written in the MIZAR language whose correctness is verified by the MIZAR processor. This effort was originally motivated by the question of whether or not the MIZAR system was sufficiently developed for the task of expressing advanced mathematics. The current state of the formalization – 57 MIZAR articles written by 16 authors – indicates that in principle the MIZAR system has successfully met the challenge. To our knowledge it is the most sizable effort aimed at mechanically checking some substantial and relatively recent field of advanced mathematics. However, it does not mean that doing mathematics in MIZAR is as simple as doing mathematics traditionally (if doing mathematics is simple at all). The work of formalizing the material of the Gierz et al. compendium has (i) prompted many improvements of the MIZAR proof checking system, (ii) caused numerous revisions of the the MIZAR data base, and (iii) contributed to the “to do” list of further changes to the MIZAR system.

This article is the eighteenth of a series of articles discussing various open research problems in automated reasoning. The problem proposed for research asks one to find criteria for choosing the type of subsumption (if any) to use for completing a specific assignment. Since subsumption can be expensive (in terms of computer time), the application of such criteria to select the most effective variant of subsumption for attacking a specific problem might materially affect the liklihood of success. As possible test problems for evaluating a proposed solution to this research problem, we suggest SAM's lemma, theorems from Tarskian geometry, and theorems from equivalential calculus.

We describe two checkers for verifying termination and reduction properties about higher-order logic programs. The reduction checker verifies that the result of a program execution is structurally smaller than (or equal to) the inputs to the program. The termination checker guarantees that the inputs of the recursive calls are structurally smaller than the inputs of the original call, taking into account reduction properties. At the heart of both checkers lies an inference system to reason about structural properties, which are described by higher-order subterm relations. This approach provides a logical foundation for proving properties such as termination and reduction and factors the effort required for each one of them. Moreover, it allows the study of proof-theoretical properties, soundness, and completeness and different optimizations. The termination and reduction checker are implemented as part of the Twelf system and have been used on a wide variety of examples, including proofs about typed assembly language and those in the area of proof-carrying code.

This paper describes an hierarchical deduction proof procedure. This procedure proves a theorem by searching for a proof acceptable to an hierarchical deduction structire; those derivations which are irrelevant to this proof are limited by means of a set of completeness-preserving refinements of the basic procedure, such as constraints on framed literals and on common tails, a proper reduction refinement, a global subsumption constraint, and a level subgoal reordering refinement, etc. In addition to this basic algorithm, we will present a partial set of support strategy and a semantically guided hierarchical deduction for the incorporation of semantics and human factors. The paper concludes with proofs concerning the completeness of the basic algorithm and the results of a computer implementation applied to some nontrivial problems.