FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
Fast cut-elimination using proof terms: an empirical study

Author: Gabriel Ebner

Paper Information

Title:Fast cut-elimination using proof terms: an empirical study
Authors:Gabriel Ebner
Proceedings:CL&C Full papers and abstracts
Editor: Stefano Berardi
Keywords:cut-elimination, proof terms, Herbrand's theorem, expansion proofs
Abstract:

ABSTRACT. Urban and Bierman introduced a calculus of proof terms for the sequent calculus LK with a strongly normalizing reduction relation. We extend this calculus to simply-typed higher-order logic with inferences for induction and equality, albeit without strong normalization. We implement this calculus in GAPT, our library for proof transformations. Evaluating the normalization on both artificial and real-world benchmarks, we show that this algorithm is typically several orders of magnitude faster than the existing Gentzen-like cut-reduction, and an order of magnitude faster than any other cut-elimination procedure implemented in GAPT.

Pages:15
Talk:Jul 07 11:00 (Session 26A)
Paper: