Typed Lambda Calculi and Applications: 7th International Conference, TLCA 2005, Nara, Japan, April 21-23, 2005. Proceedings

Thierry Coquand (auth.), Paweł Urzyczyn (eds.)3540255931, 9783540255932

The 7th International Conference on Typed Lambda Calculi and Applications (TLCA 2005) was held in Nara (Japan) from 21 to 23 April 2005, as part of the Joint Conference on Rewriting, Deduction and Programming (RDP 2005). This book contains the contributed papers, and extended abstracts of two invited talks, given by Thierry Coquand and Susumu Hayashi. A short abstract of the joint RDP invited lecture by Amy Felty is also included. The 27 contributed papers were selected from 61 submissions of generally very high quality, and the Program Committee had a hard time making the selection. The editor would like to thank everyone who submitted a paper and to express his regret that many interesting works could not be included. The editor also wishes to thank the invited speakers, the members of the Program and Organizing Committees, the Publicity Chair, and the referees for their joint e?ort towards the success of the conference. The support from the Nara Convention Bureau is gratefully acknowledged. The typed lambda calculus continues to be an important tool in logic and theoretical computer science. Since 1993, the research progress in this area has been documented by the TLCA proceedings. The present volume contributes to this tradition.

---

Table of contents :
Front Matter….Pages –
Completeness Theorems and λ -Calculus….Pages 1-9
A Tutorial Example of the Semantic Approach to Foundational Proof-Carrying Code: Abstract….Pages 10-10
Can Proofs Be Animated By Games?….Pages 11-22
Untyped Algorithmic Equality for Martin-Löf’s Logical Framework with Surjective Pairs….Pages 23-38
The Monadic Second Order Theory of Trees Given by Arbitrary Level-Two Recursion Schemes Is Decidable….Pages 39-54
A Feasible Algorithm for Typing in Elementary Affine Logic….Pages 55-70
Practical Inference for Type-Based Termination in a Polymorphic Setting….Pages 71-85
Relational Reasoning in a Nominal Semantics for Storage….Pages 86-101
Filters on CoInductive Streams, an Application to Eratosthenes’ Sieve….Pages 102-115
Recursive Functions with Higher Order Domains….Pages 116-130
Elementary Affine Logic and the Call-by-Value Lambda Calculus….Pages 131-145
Rank-2 Intersection and Polymorphic Recursion….Pages 146-161
Arithmetical Proofs of Strong Normalization Results for the Symmetric λμ -Calculus….Pages 162-178
Subtyping Recursive Types Modulo Associative Commutative Products….Pages 179-193
Galois Embedding from Polymorphic Types into Existential Types….Pages 194-208
On the Degeneracy of Σ-Types in Presence of Computational Classical Logic….Pages 209-220
Semantic Cut Elimination in the Intuitionistic Sequent Calculus….Pages 221-233
The Elimination of Nesting in SPCF….Pages 234-245
Naming Proofs in Classical Propositional Logic….Pages 246-261
Reducibility and ⊤ ⊤-Lifting for Computation Types….Pages 262-277
Privacy in Data Mining Using Formal Methods….Pages 278-292
L 3 : A Linear Language with Locations….Pages 293-307
Binding Signatures for Generic Contexts….Pages 308-323
Proof Contexts with Late Binding….Pages 324-338
The $nabla$ -Calculus. Functional Programming with Higher-Order Encodings….Pages 339-353
A Lambda Calculus for Quantum Computation with Classical Control….Pages 354-368
Continuity and Discontinuity in Lambda Calculus….Pages 369-385
Call-by-Name and Call-by-Value as Token-Passing Interaction Nets….Pages 386-400
Avoiding Equivariance in Alpha-Prolog….Pages 401-416
Higher-Order Abstract Non-interference….Pages 417-432
Back Matter….Pages –