No Cover Image

Journal article 1134 views

Separation results for the size of constant-depth propositional proofs

Arnold Beckmann Orcid Logo, Samuel R Buss

Annals of Pure and Applied Logic, Volume: 136, Issue: 1-2, Pages: 30 - 55

Swansea University Author: Arnold Beckmann Orcid Logo

Full text not available from this repository: check for access using links below.

Check full text

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

Abstract

This paper proves exponential separations between depth d-LK and depth (d+1/2)-LK for every d in 0, 1/2, 1, 1 1/2,... utilizing the order induction principle. As a consequence, we obtain an exponential separation between depth d-LK and depth (d+1)-LK for d in 0,1,2,... . We investigate the relations...

Full description

Published in: Annals of Pure and Applied Logic
ISSN: 0168-0072
Published: 2005
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa13720
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2013-07-23T12:10:46Z
last_indexed 2018-02-09T04:44:36Z
id cronfa13720
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2013-10-17T11:48:51.6027041</datestamp><bib-version>v2</bib-version><id>13720</id><entry>2012-12-17</entry><title>Separation results for the size 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>2012-12-17</date><deptcode>SCS</deptcode><abstract>This paper proves exponential separations between depth d-LK and depth (d+1/2)-LK for every d in 0, 1/2, 1, 1 1/2,... utilizing the order induction principle. As a consequence, we obtain an exponential separation between depth d-LK and depth (d+1)-LK for d in 0,1,2,... . We investigate the relationship between the sequence-size, tree-size and height of depth d-LK-derivations for d in 0, 1/2, 1, 1 1/2,... and describe transformations between them.</abstract><type>Journal Article</type><journal>Annals of Pure and Applied Logic</journal><volume>136</volume><journalNumber>1-2</journalNumber><paginationStart>30</paginationStart><paginationEnd>55</paginationEnd><publisher/><placeOfPublication/><issnPrint>0168-0072</issnPrint><issnElectronic/><keywords/><publishedDay>31</publishedDay><publishedMonth>12</publishedMonth><publishedYear>2005</publishedYear><publishedDate>2005-12-31</publishedDate><doi>10.1016/j.apal.2005.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>2013-10-17T11:48:51.6027041</lastEdited><Created>2012-12-17T10:22:50.7350819</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>Samuel R</firstname><surname>Buss</surname><order>2</order></author></authors><documents/><OutputDurs/></rfc1807>
spelling 2013-10-17T11:48:51.6027041 v2 13720 2012-12-17 Separation results for the size of constant-depth propositional proofs 1439ebd690110a50a797b7ec78cca600 0000-0001-7958-5790 Arnold Beckmann Arnold Beckmann true false 2012-12-17 SCS This paper proves exponential separations between depth d-LK and depth (d+1/2)-LK for every d in 0, 1/2, 1, 1 1/2,... utilizing the order induction principle. As a consequence, we obtain an exponential separation between depth d-LK and depth (d+1)-LK for d in 0,1,2,... . We investigate the relationship between the sequence-size, tree-size and height of depth d-LK-derivations for d in 0, 1/2, 1, 1 1/2,... and describe transformations between them. Journal Article Annals of Pure and Applied Logic 136 1-2 30 55 0168-0072 31 12 2005 2005-12-31 10.1016/j.apal.2005.05.002 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2013-10-17T11:48:51.6027041 2012-12-17T10:22:50.7350819 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Arnold Beckmann 0000-0001-7958-5790 1 Samuel R Buss 2
title Separation results for the size of constant-depth propositional proofs
spellingShingle Separation results for the size of constant-depth propositional proofs
Arnold Beckmann
title_short Separation results for the size of constant-depth propositional proofs
title_full Separation results for the size of constant-depth propositional proofs
title_fullStr Separation results for the size of constant-depth propositional proofs
title_full_unstemmed Separation results for the size of constant-depth propositional proofs
title_sort Separation results for the size of constant-depth propositional proofs
author_id_str_mv 1439ebd690110a50a797b7ec78cca600
author_id_fullname_str_mv 1439ebd690110a50a797b7ec78cca600_***_Arnold Beckmann
author Arnold Beckmann
author2 Arnold Beckmann
Samuel R Buss
format Journal article
container_title Annals of Pure and Applied Logic
container_volume 136
container_issue 1-2
container_start_page 30
publishDate 2005
institution Swansea University
issn 0168-0072
doi_str_mv 10.1016/j.apal.2005.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 0
active_str 0
description This paper proves exponential separations between depth d-LK and depth (d+1/2)-LK for every d in 0, 1/2, 1, 1 1/2,... utilizing the order induction principle. As a consequence, we obtain an exponential separation between depth d-LK and depth (d+1)-LK for d in 0,1,2,... . We investigate the relationship between the sequence-size, tree-size and height of depth d-LK-derivations for d in 0, 1/2, 1, 1 1/2,... and describe transformations between them.
published_date 2005-12-31T03:15:41Z
_version_ 1763750278421544960
score 11.014291

Similar Items