Abstract
Tait's method (a.k.a. proof by logical relations) is a powerful proof technique frequently used for showing foundational properties of languages based on typed lambda-calculi. Historically, these proofs have been extremely difficult to formalize in proof assistants with weak meta-logics, such as Twelf, and yet they are often straightforward in proof assistants with stronger meta-logics. In this paper, we propose structural logical relations as a technique for conducting these proofs in systems with limited meta-logical strength by explicitly representing and reasoning about an auxiliary logic. In support of our claims, we give a Twelf-checked proof of the completeness of an algorithm for checking equality of simply typed lambda-terms.
Originalsprog | Engelsk |
---|---|
Tidsskrift | Logic in Computer Science |
Sider (fra-til) | 69-82 |
ISSN | 1043-6871 |
Status | Udgivet - 2008 |
Begivenhed | 23rd Annual IEEE Symposium on Logic in Computer Science (LICS 2008) - Pittsburgh, Pennsylvania, USA Varighed: 24 jun. 2008 → 27 jun. 2008 Konferencens nummer: 23 |
Konference
Konference | 23rd Annual IEEE Symposium on Logic in Computer Science (LICS 2008) |
---|---|
Nummer | 23 |
Land/Område | USA |
By | Pittsburgh, Pennsylvania |
Periode | 24/06/2008 → 27/06/2008 |
Emneord
- Tait's method
- proof by logical relations
- typed lambda-calculi
- proof formalization
- structural logical relations