Curry-Howard for sequent calculus at last!
| Data(s) |
12/06/2015
|
|---|---|
| Resumo |
This paper tries to remove what seems to be the remaining stumbling blocks in the way to a full understanding of the Curry-Howard isomorphism for sequent calculus, namely the questions: What do variables in proof terms stand for? What is co-control and a co-continuation? How to define the dual of Parigot's mu-operator so that it is a co-control operator? Answering these questions leads to the interpretation that sequent calculus is a formal vector notation with first-class co-control. But this is just the "internal" interpretation, which has to be developed simultaneously with, and is justified by, an "external" one, offered by natural deduction: the sequent calculus corresponds to a bi-directional, agnostic (w.r.t. the call strategy), computational lambda-calculus. Next, the duality between control and co-control is studied and proved in the context of classical logic, where one discovers that the classical sequent calculus has a distortion towards control, and that sequent calculus is the de Morgan dual of natural deduction. |
| Identificador |
http://hdl.handle.net/1822/39302 10.4230/LIPIcs.TLCA.2015.165 |
| Idioma(s) |
eng |
| Publicador |
Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik |
| Relação |
PEst-OE/MAT/UI0013/2014 |
| Direitos |
info:eu-repo/semantics/openAccess |
| Palavras-Chave | #Co-control #Co-continuation #Vector notation #Let-expression #Formal substitution #Context substitution #Computational lambda-calculus #Classical logic #de Morgan duality |
| Tipo |
info:eu-repo/semantics/conferenceObject |