Proof Theory in Computer Science: International Seminar, PTCS 2001 Dagstuhl Castle, Germany, October 7–12, 2001 Proceedings

Klaus Aehlig, Jan Johannsen, Helmut Schwichtenberg (auth.), Reinhard Kahle, Peter Schroeder-Heister, Robert Stärk (eds.)354042752X, 9783540427520

Proof theory has long been established as a basic discipline of mathematical logic. It has recently become increasingly relevant to computer science. The – ductive apparatus provided by proof theory has proved useful for metatheoretical purposes as well as for practical applications. Thus it seemed to us most natural to bring researchers together to assess both the role proof theory already plays in computer science and the role it might play in the future. The form of a Dagstuhl seminar is most suitable for purposes like this, as Schloß Dagstuhl provides a very convenient and stimulating environment to – scuss new ideas and developments. To accompany the conference with a proc- dings volume appeared to us equally appropriate. Such a volume not only ?xes basic results of the subject and makes them available to a broader audience, but also signals to the scienti?c community that Proof Theory in Computer Science (PTCS) is a major research branch within the wider ?eld of logic in computer science.

---

Table of contents :
Linear Ramified Higher Type Recursion and Parallel Complexity….Pages 1-21
Reflective λ-Calculus….Pages 22-37
A Note on the Proof-Theoretic Strength of a Single Application of the Schema of Identity….Pages 38-48
Comparing the Complexity of Cut-Elimination Methods….Pages 49-67
Program Extraction from Gentzen’s Proof of Transfinite Induction up to ε 0 ….Pages 68-77
Coherent Bicartesian and Sesquicartesian Categories….Pages 78-92
Indexed Induction-Recursion….Pages 93-113
Modeling Meta-logical Features in a Calculus with Frozen Variables….Pages 114-129
Proof Theory and Post-turing Analysis….Pages 130-152
Interpolation for Natural Deduction with Generalized Eliminations….Pages 153-169
Implicit Characterizations of Pspace ….Pages 170-190
Iterate logic….Pages 191-201
Constructive Foundations for Featherweight Java….Pages 202-238