Types for Proofs and Programs

This book contains a selection of papers presented at the ?rst annual workshop of the TYPES Working Group (Computer-Assisted Reasoning Based on Type Theory, EU IST project 29001), which was held 8th 12th of December, 2000 at the University of Durham, Durham, UK. It was attended by about 80 researchers. The workshop follows a series of meetings organised in 1993, 1994, 1995, 1996, 1998, and 1999 under the auspices of the Esprit BRA6435 and the - prit Working Group 21900 for the previous TYPES projects. Those proceedings were also published in the LNCS series, edited by Henk Barendregt and Tobias Nipkow (Vol. 806, 1993), by Peter Dybjer, Bengt Nordstr om, and Jan Smith (Vol. 996, 1994), by Stefano Berardi and Mario Coppo (Vol. 1158, 1995), by Christine Paulin-Mohring and Eduardo Gimenez (Vol. 1512, 1996), by Thorsten Altenkirch, Wolfgang Naraschewski, and Bernhard Reus (Vol. 1657, 1998), and by Thierry Coquand, Peter Dybjer, Bengt Nordstr om, and Jan Smith (Vol. 1956, 1999). The Esprit BRA6453 was itself a continuation of the former Esprit - tion 3245, Logical Frameworks: Design, Implementation, and Experiments. The articles from the annual workshops under that Action were edited by Gerard Huet and Gordon Plotkin in the books Logical Frameworks and Logical En- ronments, both published by Cambridge University Press. Acknowledgements We are very grateful to members of Durham s Computer Assisted Reasoning Group, especially Robert Kießling, for helping to organise the workshop. Robert s contribution was key to the success of the meeting.

Includes supplementary material: sn.pub/extras

Inhalt
Collection Principles in Dependent Type Theory.- Executing Higher Order Logic.- A Tour with Constructive Real Numbers.- An Implementation of Type:Type.- On the Logical Content of Computational Type Theory: A Solution to Curry's Problem.- Constructive Reals in Coq: Axioms and Categoricity.- A Constructive Proof of the Fundamental Theorem of Algebra without Using the Rationals.- A Kripke-Style Model for the Admissibility of Structural Rules.- Towards Limit Computable Mathematics.- Formalizing the Halting Problem in a Constructive Type Theory.- On the Proofs of Some Formally Unprovable Propositions and Prototype Proofs in Type Theory.- Changing Data Structures in Type Theory: A Study of Natural Numbers.- Elimination with a Motive.- Generalization in Type Theory Based Proof Assistants.- An Inductive Version of Nash-Williams' Minimal-Bad-Sequence Argument for Higman's Lemma.