Campus Event Calendar
Event Entry
New for: D3
What and Who
New lower bounds for the typed lambda calculus and higher-order matching
Sergei Vorobyov
MPII
Logik-Seminar
AG 1, AG 2, AG 3, AG 4
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 12 August 99
16:15
60 Minutes
46
024
Saarbrücken
Abstract
We give a new straightforward proof of the famous Statman's
theorem (that the simply typed lambda calculus is not elementary
recursive), which implies the new stronger lower bounds for
the bounded-order fragments of the calculus and the higher-order
matching problem. In particular:
1) (k+6)-th order lambda calculus is k-DEXPTIME hard
2) (k+7)-th order matching is k-DEXPTIME hard
Contact
Sergei Vorobyov
329
--email hidden
passcode not visible
logged in users only