No Cover Image

Journal article 859 views 90 downloads

On transformations of constant depth propositional proofs

Arnold Beckmann Orcid Logo, Sam Buss

Annals of Pure and Applied Logic

Swansea University Author: Arnold Beckmann Orcid Logo

  • RevisedVersion_Archival_Oct28_2018.pdf

    PDF | Accepted Manuscript

    Released under the terms of a Creative Commons Attribution Non-Commercial No Derivatives License (CC-BY-NC-ND).

    Download (301.82KB)

Check full text

DOI (Published version): 10.1016/j.apal.2019.05.002

Abstract

This paper studies the complexity of constant depth propositional proofs in the cedent and sequent calculus. We discuss the relationships between the size of tree-like proofs, the size of dag-like proofs, and the heights of proofs. The main result is to correct a proof construction in an earlier pap...

Full description

Published in: Annals of Pure and Applied Logic
ISSN: 01680072
Published: 2019
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa50215
Tags: Add Tag
No Tags, Be the first to tag this record!
Abstract: This paper studies the complexity of constant depth propositional proofs in the cedent and sequent calculus. We discuss the relationships between the size of tree-like proofs, the size of dag-like proofs, and the heights of proofs. The main result is to correct a proof construction in an earlier paper about transformations from proofs with polylogarithmic height and constantly many formulas per cedent.
College: Faculty of Science and Engineering

Similar Items