## Proof Theory in Computer Science: International Seminar, PTCS 2001 Dagstuhl Castle, Germany, October 7-12, 2001. ProceedingsProof 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Linear Ramified Higher Type Recursion and Parallel Complexity | 1 |

Reflective λCalculus | 22 |

A Note on the ProofTheoretic Strength of a Single Application of the Schema of Identity | 38 |

Comparing the Complexity of CutElimination Methods | 49 |

Program Extraction from Gentzens Proof of Transfinite Induction up to ε0 | 68 |

Coherent Bicartesian and Sesquicartesian Categories | 78 |

Indexed InductionRecursion | 93 |

Modeling Metalogical Features in a Calculus with Frozen Variables | 114 |

Proof Theory and Postturing Analysis | 130 |

Interpolation for Natural Deduction with Generalized Eliminations | 153 |

Implicit Characterizations of Pspace | 170 |

Iterate Logic | 191 |

Constructive Foundations for Featherweight Java | 202 |

Author Index | 239 |

### Other editions - View all

### Common terms and phrases

apply argument Bellantoni bicartesian category binary bounded calculus coherence computability predicates Computer Science constant constructor context corresponding cut-elimination cut-elimination sequence cut-free deﬁned deﬁnition denotational semantics denote derivation elimination equal example expression Featherweight Java finite ﬁrst ﬁxed fixed point formula free variables FSubst function symbol functor FV(g G NF Gentzen Hence higher type identity axioms impredicative induction hypothesis inductive-recursive definitions input instances interpretation intuitionistic intuitionistic logic isomorphic K-term language least fixed point Lemma length linear logic Martin-Löf type theory method natural numbers node normal form object object-oriented programming obtain occurs operational semantics operations ordinal polynomial predicate primitive recursion processors proof theory proof-theoretic propositional provable prove Pspace recursion on notation reduction result rewriting rules semantics sequent slice category subterm term of type Theorem transfinite induction tree type theory type variable