License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2015.94
URN: urn:nbn:de:0030-drops-54097
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5409/
Go to the corresponding LIPIcs Volume Portal

Baaz, Matthias ; Fermüller, Christian G.

Elementary Elimination of Prenex Cuts in Disjunction-free Intuitionistic Logic

pdf-format:
6.pdf (0.5 MB)

Abstract

The size of shortest cut-free proofs of first-order formulas in intuitionistic sequent calculus is known to be non-elementary in the worst case in terms of the size of given sequent proofs with cuts of the same formulas. In contrast to that fact, we provide an elementary bound for the size of cut-free proofs for disjunction-free intuitionistic logic for the case where the cut-formulas of the original proof are prenex. Moreover, we establish non-elementary lower bounds for classical disjunction-free proofs with prenex cut-formulas and intuitionistic disjunction-free proofs with non-prenex cut-formulas.

BibTeX - Entry

@InProceedings{baaz_et_al:LIPIcs:2015:5409,
  author =	{Matthias Baaz and Christian G. Ferm{\"u}ller},
  title =	{{Elementary Elimination of Prenex Cuts in Disjunction-free Intuitionistic Logic}},
  booktitle =	{24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
  pages =	{94--109},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-90-3},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{41},
  editor =	{Stephan Kreutzer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5409},
  URN =		{urn:nbn:de:0030-drops-54097},
  doi =		{10.4230/LIPIcs.CSL.2015.94},
  annote =	{Keywords: Cut-elimination, sequent calculus, intuitionistic logic}
}

Keywords: Cut-elimination, sequent calculus, intuitionistic logic
Collection: 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)
Issue Date: 2015
Date of publication: 07.09.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI