No Cover Image

Journal article 174 views 8 downloads

On transformations of constant depth propositional proofs / Arnold Beckmann; Sam Buss

Annals of Pure and Applied Logic

Swansea University Author: Arnold, Beckmann

  • 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)

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: College of Science