Miquel, Alexandre - Existential witness extraction in classical realizability and via a negative translation

lmcs:1068 - Logical Methods in Computer Science, April 22, 2011, Volume 7, Issue 2
Existential witness extraction in classical realizability and via a negative translation

Authors: Miquel, Alexandre

We show how to extract existential witnesses from classical proofs using Krivine's classical realizability---where classical proofs are interpreted as lambda-terms with the call/cc control operator. We first recall the basic framework of classical realizability (in classical second-order arithmetic) and show how to extend it with primitive numerals for faster computations. Then we show how to perform witness extraction in this framework, by discussing several techniques depending on the shape of the existential formula. In particular, we show that in the Sigma01-case, Krivine's witness extraction method reduces to Friedman's through a well-suited negative translation to intuitionistic second-order arithmetic. Finally we discuss the advantages of using call/cc rather than a negative translation, especially from the point of view of an implementation.


Source : oai:arXiv.org:1101.4364
DOI : 10.2168/LMCS-7(2:2)2011
Volume: Volume 7, Issue 2
Published on: April 22, 2011
Submitted on: November 21, 2009
Keywords: Computer Science - Logic in Computer Science,F.4.1


Share

Consultation statistics

This page has been seen 75 times.
This article's PDF has been downloaded 23 times.