No Cover Image

Journal article 1106 views

An unexpected separation result in Linearly Bounded Arithmetic

Arnold Beckmann Orcid Logo, Jan Johannsen

MLQ, Volume: 51, Issue: 2, Pages: 191 - 200

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.1002/malq.200410019

Abstract

The theories S i 1 (α) and T i 1 (α) are the analogues of Buss' relativized bounded arithmetic theories in the language where every term is bounded by a polynomial, and thus all definable functions grow linearly in length. For every i , a Σ b i+1 (α) - formula TOPi(α) , which expresses a form o...

Full description

Published in: MLQ
ISSN: 0942-5616 1521-3870
Published: 2005
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa13721
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 cronfa13721
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2013-10-17T11:49:10.7665259</datestamp><bib-version>v2</bib-version><id>13721</id><entry>2012-12-17</entry><title>An unexpected separation result in Linearly Bounded Arithmetic</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>The theories S i 1 (&#x3B1;) and T i 1 (&#x3B1;) are the analogues of Buss' relativized bounded arithmetic theories in the language where every term is bounded by a polynomial, and thus all definable functions grow linearly in length. For every i , a &#x3A3; b i+1 (&#x3B1;) - formula TOPi(&#x3B1;) , which expresses a form of the total ordering principle, is exhibited that is provable in S i+1 1 (&#x3B1;) , but unprovable in T i 1 (&#x3B1;) . This is in contrast with the classical situation, where S i+1 2 is conservative over T i 2 w.r.t. &#x3A3; b i+1 -sentences. The independence results are proved by translations into propositional logic, and using lower bounds for corresponding propositional proof systems.</abstract><type>Journal Article</type><journal>MLQ</journal><volume>51</volume><journalNumber>2</journalNumber><paginationStart>191</paginationStart><paginationEnd>200</paginationEnd><publisher/><placeOfPublication/><issnPrint>0942-5616</issnPrint><issnElectronic>1521-3870</issnElectronic><keywords/><publishedDay>31</publishedDay><publishedMonth>12</publishedMonth><publishedYear>2005</publishedYear><publishedDate>2005-12-31</publishedDate><doi>10.1002/malq.200410019</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:49:10.7665259</lastEdited><Created>2012-12-17T10:23:38.0962755</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>Jan</firstname><surname>Johannsen</surname><order>2</order></author></authors><documents/><OutputDurs/></rfc1807>
spelling 2013-10-17T11:49:10.7665259 v2 13721 2012-12-17 An unexpected separation result in Linearly Bounded Arithmetic 1439ebd690110a50a797b7ec78cca600 0000-0001-7958-5790 Arnold Beckmann Arnold Beckmann true false 2012-12-17 SCS The theories S i 1 (α) and T i 1 (α) are the analogues of Buss' relativized bounded arithmetic theories in the language where every term is bounded by a polynomial, and thus all definable functions grow linearly in length. For every i , a Σ b i+1 (α) - formula TOPi(α) , which expresses a form of the total ordering principle, is exhibited that is provable in S i+1 1 (α) , but unprovable in T i 1 (α) . This is in contrast with the classical situation, where S i+1 2 is conservative over T i 2 w.r.t. Σ b i+1 -sentences. The independence results are proved by translations into propositional logic, and using lower bounds for corresponding propositional proof systems. Journal Article MLQ 51 2 191 200 0942-5616 1521-3870 31 12 2005 2005-12-31 10.1002/malq.200410019 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2013-10-17T11:49:10.7665259 2012-12-17T10:23:38.0962755 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Arnold Beckmann 0000-0001-7958-5790 1 Jan Johannsen 2
title An unexpected separation result in Linearly Bounded Arithmetic
spellingShingle An unexpected separation result in Linearly Bounded Arithmetic
Arnold Beckmann
title_short An unexpected separation result in Linearly Bounded Arithmetic
title_full An unexpected separation result in Linearly Bounded Arithmetic
title_fullStr An unexpected separation result in Linearly Bounded Arithmetic
title_full_unstemmed An unexpected separation result in Linearly Bounded Arithmetic
title_sort An unexpected separation result in Linearly Bounded Arithmetic
author_id_str_mv 1439ebd690110a50a797b7ec78cca600
author_id_fullname_str_mv 1439ebd690110a50a797b7ec78cca600_***_Arnold Beckmann
author Arnold Beckmann
author2 Arnold Beckmann
Jan Johannsen
format Journal article
container_title MLQ
container_volume 51
container_issue 2
container_start_page 191
publishDate 2005
institution Swansea University
issn 0942-5616
1521-3870
doi_str_mv 10.1002/malq.200410019
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 The theories S i 1 (α) and T i 1 (α) are the analogues of Buss' relativized bounded arithmetic theories in the language where every term is bounded by a polynomial, and thus all definable functions grow linearly in length. For every i , a Σ b i+1 (α) - formula TOPi(α) , which expresses a form of the total ordering principle, is exhibited that is provable in S i+1 1 (α) , but unprovable in T i 1 (α) . This is in contrast with the classical situation, where S i+1 2 is conservative over T i 2 w.r.t. Σ b i+1 -sentences. The independence results are proved by translations into propositional logic, and using lower bounds for corresponding propositional proof systems.
published_date 2005-12-31T03:15:41Z
_version_ 1763750278544228352
score 11.014291

Similar Items