SPECIAL ISSUE:
Special Issue: Types for Proofs and Programs, 2010
Warsaw, Poland, 2010



Preface



This special issue of Logical Methods in Computer Science (LMCS) is devoted to the recent progress in the technology of formal methods: notably the design and verification of software, hardware, and mathematics based on type theory. It continues the tradition originated by several books published by Springer under the same title since 1993. The issue consists of nine articles selected out of 22 submissions resulting from an open call for papers circulated in the Types community. These papers cover various aspects of constructive type theory and its applications, in particular formalizing mathematics and issues related to proof-assistants and proof technology. Papers on the following topics are included:

(1) lambda-calculus and logic;
(2) type theories;
(3) proof assistants;
(4) formalization.

As to 1, Denis Cousineau's paper "On completeness of reducibility candidates as a semantics of strong normalization" provides a semantical characterization of the strong normalization property for theories in deduction modulo a la Curry: a theory is strongly normalizing iff it admits a certain model.
Then Pablo Arrighi and Alejandro Daz-Caro wrote "A System F accounting for scalars", which studies a variant of polymorphic type assignment (system F) to the linear algebraic lambda-calculus, where linear combinations of lambda-terms are possible.
With "On streams that are finitely red" Marc Bezem, Keiko Nakata, and Tarmo Uustalu study constructive definitions of the notion of finiteness, in particular relations between various constructive interpretations of the quantifier "almost every".
As to 2, in the paper of James Cheney "A dependent nominal type theory", an LF-style dependent type theory is proposed which provides a type-theoretic framework for the nominal approach to abstract syntax.
Then "On Irrelevance and Algorithmic Equality in Predicative Type Theory", by Andreas Abel and Gabriel Scherer, proposes a type theory for dependently typed programs, extending the Martin-Lof type theory by so called irrelevant quantifiers (another form of dependent product). The motivation for this work is eliminating computationally irrelevant code at compile time.
As to 3, in "A Synthesis of the Procedural and Declarative Styles of Interactive Theorem Proving", by Freek Wiedijk, a new generic approach is proposed to combine the procedural and declarative styles of interactive theorem proving. The method is fully implemented as a proof interface miz3.
In "A bi-directional refinement algorithm for the calculus of (co)inductive constructions" Andrea Asperti, Wilmer Ricciotti, Claudio Sacerdoti Coen, and Enrico Tassi describe a type inference algorithm for the Calculus of Inductive Constructions, as implemented in the Matita theorem prover.
As to 4, in "Formal proofs in real algebraic geometry: from ordered fields to quantifier elimination", Assia Mahboubi and Cyril Cohen provide a formalization in Coq of the theory of discrete real closed fields, which captures in particular a computational formalization of algebraic numbers.
Finally Thomas Braibant and Damien Pous provide with their paper "Deciding Kleene Algebras in Coq" a high-level Coq tactic to decide equations in Kleene algebras, thus making progress in developing tools to handle binary relations in Coq.
The craftmanship of turning mathematics into lambda terms as formal proofs has been developing impressively in the period 1970-2012. In 1970 the first (not yet interactive) systems of Automath by N.G. de Bruijn and collaborators started to be used for formalization (and hence checking). During the last decade highly non trivial mathematical formalization results have been established in type theory (system Coq): Four Colour Theorem (2005), Feit-Thompson theorem (2012), by Georges Gonthier and collaborators. In spite of the possibility of formalizing, the craftmanship to do so remains a time consuming skill. We hope that this issue eventually contributes to turning mathematics into formal proofs in a less labour consuming way.

The Editors wish to thank all authors for their submissions to this special issue, as well as all the anonymous reviewers.

Henk Barendregt and Pawel Urzyczyn
Special Issue Editors




Full Text: PDF

Creative Commons