Beschreibung:
This article examines the computational content of the classical Gentzen sequent calculus. There are a number of well-known methods that extract computational content from first-order logic but applying these to the sequent calculus involves first translating proofs into other formalisms, Hilbert calculi or Natural Deduction for example. A direct approach which mirrors the symmetry inherent in sequent calculus has potential merits in relation to proof-theoretic considerations such as the (non-)confluence of cut elimination, the problem of cut introduction, proof compression and proof equivalence. Motivated by such applications, we provide a representation of sequent calculus proofs as higher order recursion schemes. Our approach associates to an LK proof pi of double right arrow there exists nu F, where F is quantifier free, an acyclic higher order recursion scheme H with a finite language yielding a Herbrand disjunction for there exists nu F. More generally, we show that the language of H contains all Herbrand disjunctions computable from pi via a broad range of cut elimination strategies.