No Cover Image

Journal article 985 views 107 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!
first_indexed 2019-06-05T11:06:46Z
last_indexed 2019-06-14T20:49:54Z
id cronfa50215
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2019-06-14T11:42:01.1296784</datestamp><bib-version>v2</bib-version><id>50215</id><entry>2019-05-02</entry><title>On transformations of constant depth propositional proofs</title><swanseaauthors><author><sid>1439ebd690110a50a797b7ec78cca600</sid><ORCID>0000-0001-7958-5790</ORCID><firstname>Arnold</firstname><surname>Beckmann</surname><name>Arnold Beckmann</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2019-05-02</date><deptcode>SCS</deptcode><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.</abstract><type>Journal Article</type><journal>Annals of Pure and Applied Logic</journal><publisher/><issnPrint>01680072</issnPrint><keywords/><publishedDay>31</publishedDay><publishedMonth>12</publishedMonth><publishedYear>2019</publishedYear><publishedDate>2019-12-31</publishedDate><doi>10.1016/j.apal.2019.05.002</doi><url/><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><lastEdited>2019-06-14T11:42:01.1296784</lastEdited><Created>2019-05-02T22:14:42.5847264</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Arnold</firstname><surname>Beckmann</surname><orcid>0000-0001-7958-5790</orcid><order>1</order></author><author><firstname>Sam</firstname><surname>Buss</surname><order>2</order></author></authors><documents><document><filename>0050215-02052019221845.pdf</filename><originalFilename>RevisedVersion_Archival_Oct28_2018.pdf</originalFilename><uploaded>2019-05-02T22:18:45.2100000</uploaded><type>Output</type><contentLength>260683</contentLength><contentType>application/pdf</contentType><version>Accepted Manuscript</version><cronfaStatus>true</cronfaStatus><embargoDate>2020-05-15T00:00:00.0000000</embargoDate><documentNotes>Released under the terms of a Creative Commons Attribution Non-Commercial No Derivatives License (CC-BY-NC-ND).</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language></document></documents><OutputDurs/></rfc1807>
spelling 2019-06-14T11:42:01.1296784 v2 50215 2019-05-02 On transformations of constant depth propositional proofs 1439ebd690110a50a797b7ec78cca600 0000-0001-7958-5790 Arnold Beckmann Arnold Beckmann true false 2019-05-02 SCS 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. Journal Article Annals of Pure and Applied Logic 01680072 31 12 2019 2019-12-31 10.1016/j.apal.2019.05.002 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2019-06-14T11:42:01.1296784 2019-05-02T22:14:42.5847264 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Arnold Beckmann 0000-0001-7958-5790 1 Sam Buss 2 0050215-02052019221845.pdf RevisedVersion_Archival_Oct28_2018.pdf 2019-05-02T22:18:45.2100000 Output 260683 application/pdf Accepted Manuscript true 2020-05-15T00:00:00.0000000 Released under the terms of a Creative Commons Attribution Non-Commercial No Derivatives License (CC-BY-NC-ND). true eng
title On transformations of constant depth propositional proofs
spellingShingle On transformations of constant depth propositional proofs
Arnold Beckmann
title_short On transformations of constant depth propositional proofs
title_full On transformations of constant depth propositional proofs
title_fullStr On transformations of constant depth propositional proofs
title_full_unstemmed On transformations of constant depth propositional proofs
title_sort On transformations of constant depth propositional proofs
author_id_str_mv 1439ebd690110a50a797b7ec78cca600
author_id_fullname_str_mv 1439ebd690110a50a797b7ec78cca600_***_Arnold Beckmann
author Arnold Beckmann
author2 Arnold Beckmann
Sam Buss
format Journal article
container_title Annals of Pure and Applied Logic
publishDate 2019
institution Swansea University
issn 01680072
doi_str_mv 10.1016/j.apal.2019.05.002
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
document_store_str 1
active_str 0
description 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.
published_date 2019-12-31T04:01:34Z
_version_ 1763753165662978048
score 11.03559

Similar Items