Structural Logical Relations

Carsten Schürmann, Jeffrey Sarnat

Publikation: Artikel i tidsskrift og konference artikel i tidsskriftKonferenceartikelForskningpeer review

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.
OriginalsprogEngelsk
TidsskriftLogic in Computer Science
Sider (fra-til)69-82
ISSN1043-6871
StatusUdgivet - 2008
Begivenhed23rd Annual IEEE Symposium on Logic in Computer Science (LICS 2008) - Pittsburgh, Pennsylvania, USA
Varighed: 24 jun. 200827 jun. 2008
Konferencens nummer: 23

Konference

Konference23rd Annual IEEE Symposium on Logic in Computer Science (LICS 2008)
Nummer23
Land/OmrådeUSA
ByPittsburgh, Pennsylvania
Periode24/06/200827/06/2008

Emneord

  • Tait's method
  • proof by logical relations
  • typed lambda-calculi
  • proof formalization
  • structural logical relations

Citationsformater