No Cover Image

Journal article 949 views

Generalised dynamic ordinals - universal measures for implicit computational complexity

Arnold Beckmann Orcid Logo

Lecture Notes in Logic, Volume: 27, Pages: 48 - 74

Swansea University Author: Arnold Beckmann Orcid Logo

Abstract

We extend the definition of dynamic ordinals to generalised dynamic ordinals. We compute generalised dynamic ordinals of all fragments of relativised bounded arithmetic by utilising methods from Boolean complexity theory, similar to [Krajicek1994]. We indicate the role of generalised dynamic ordinal...

Full description

Published in: Lecture Notes in Logic
Published: 2006
URI: https://cronfa.swan.ac.uk/Record/cronfa13719
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:35Z
id cronfa13719
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2013-10-17T11:48:32.1087915</datestamp><bib-version>v2</bib-version><id>13719</id><entry>2012-12-17</entry><title>Generalised dynamic ordinals - universal measures for implicit computational complexity</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>We extend the definition of dynamic ordinals to generalised dynamic ordinals. We compute generalised dynamic ordinals of all fragments of relativised bounded arithmetic by utilising methods from Boolean complexity theory, similar to [Krajicek1994]. We indicate the role of generalised dynamic ordinals as universal measures for implicit computational complexity. I.e., we describe the connections between generalised dynamic ordinals and witness oracle Turing machines for bounded arithmetic theories. In particular, through the determination of generalised dynamic ordinals we re-obtain well-known independence results for relativised bounded arithmetic theories.</abstract><type>Journal Article</type><journal>Lecture Notes in Logic</journal><volume>27</volume><journalNumber></journalNumber><paginationStart>48</paginationStart><paginationEnd>74</paginationEnd><publisher/><placeOfPublication/><issnPrint/><issnElectronic/><keywords/><publishedDay>31</publishedDay><publishedMonth>12</publishedMonth><publishedYear>2006</publishedYear><publishedDate>2006-12-31</publishedDate><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:32.1087915</lastEdited><Created>2012-12-17T10:19:49.9439601</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></authors><documents/><OutputDurs/></rfc1807>
spelling 2013-10-17T11:48:32.1087915 v2 13719 2012-12-17 Generalised dynamic ordinals - universal measures for implicit computational complexity 1439ebd690110a50a797b7ec78cca600 0000-0001-7958-5790 Arnold Beckmann Arnold Beckmann true false 2012-12-17 SCS We extend the definition of dynamic ordinals to generalised dynamic ordinals. We compute generalised dynamic ordinals of all fragments of relativised bounded arithmetic by utilising methods from Boolean complexity theory, similar to [Krajicek1994]. We indicate the role of generalised dynamic ordinals as universal measures for implicit computational complexity. I.e., we describe the connections between generalised dynamic ordinals and witness oracle Turing machines for bounded arithmetic theories. In particular, through the determination of generalised dynamic ordinals we re-obtain well-known independence results for relativised bounded arithmetic theories. Journal Article Lecture Notes in Logic 27 48 74 31 12 2006 2006-12-31 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2013-10-17T11:48:32.1087915 2012-12-17T10:19:49.9439601 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Arnold Beckmann 0000-0001-7958-5790 1
title Generalised dynamic ordinals - universal measures for implicit computational complexity
spellingShingle Generalised dynamic ordinals - universal measures for implicit computational complexity
Arnold Beckmann
title_short Generalised dynamic ordinals - universal measures for implicit computational complexity
title_full Generalised dynamic ordinals - universal measures for implicit computational complexity
title_fullStr Generalised dynamic ordinals - universal measures for implicit computational complexity
title_full_unstemmed Generalised dynamic ordinals - universal measures for implicit computational complexity
title_sort Generalised dynamic ordinals - universal measures for implicit computational complexity
author_id_str_mv 1439ebd690110a50a797b7ec78cca600
author_id_fullname_str_mv 1439ebd690110a50a797b7ec78cca600_***_Arnold Beckmann
author Arnold Beckmann
author2 Arnold Beckmann
format Journal article
container_title Lecture Notes in Logic
container_volume 27
container_start_page 48
publishDate 2006
institution Swansea University
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 We extend the definition of dynamic ordinals to generalised dynamic ordinals. We compute generalised dynamic ordinals of all fragments of relativised bounded arithmetic by utilising methods from Boolean complexity theory, similar to [Krajicek1994]. We indicate the role of generalised dynamic ordinals as universal measures for implicit computational complexity. I.e., we describe the connections between generalised dynamic ordinals and witness oracle Turing machines for bounded arithmetic theories. In particular, through the determination of generalised dynamic ordinals we re-obtain well-known independence results for relativised bounded arithmetic theories.
published_date 2006-12-31T03:15:40Z
_version_ 1763750278302007296
score 11.002155

Similar Items