No Cover Image

Conference Paper/Proceeding/Abstract 917 views 749 downloads

Theory and Applications of Models of Computation

Takayuki Kihara, Arno Pauly Orcid Logo

Volume: 11436, Start page: 378

Swansea University Author: Arno Pauly Orcid Logo

Check full text

DOI (Published version): 10.1007/978-3-030-14812-6

Abstract

We study the Weihrauch degrees of closed choice for finite sets, closed choice for convex sets and sorting infinite sequences over finite alphabets. Our main result is that choice for finite sets of cardinality $i + 1$ is reducible to choice for convex sets in dimension $j$, which in turn is reducib...

Full description

ISBN: 978-3-030-14811-9 978-3-030-14812-6
ISSN: 0302-9743 1611-3349
Published: Japan 15th Annual Conference, TAMC 2019, Kitakyushu, Japan, April 13–16, 2019 2019
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa49944
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2019-04-09T13:04:51Z
last_indexed 2019-05-01T11:40:10Z
id cronfa49944
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2019-04-26T15:52:23.2707948</datestamp><bib-version>v2</bib-version><id>49944</id><entry>2019-04-08</entry><title>Theory and Applications of Models of Computation</title><swanseaauthors><author><sid>17a56a78ec04e7fc47b7fe18394d7245</sid><ORCID>0000-0002-0173-3295</ORCID><firstname>Arno</firstname><surname>Pauly</surname><name>Arno Pauly</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2019-04-08</date><deptcode>SCS</deptcode><abstract>We study the Weihrauch degrees of closed choice for finite sets, closed choice for convex sets and sorting infinite sequences over finite alphabets. Our main result is that choice for finite sets of cardinality $i + 1$ is reducible to choice for convex sets in dimension $j$, which in turn is reducible to sorting infinite sequences over an alphabet of size $k + 1$, iff $i \leq j \leq k$. Our proofs invoke Kleene's recursion theorem, and we describe in some detail how Kleene's recursion theorem gives rise to a technique for proving separations of Weihrauch degrees.</abstract><type>Conference Paper/Proceeding/Abstract</type><journal/><volume>11436</volume><paginationStart>378</paginationStart><publisher>15th Annual Conference, TAMC 2019, Kitakyushu, Japan, April 13&#x2013;16, 2019</publisher><placeOfPublication>Japan</placeOfPublication><isbnPrint>978-3-030-14811-9</isbnPrint><isbnElectronic>978-3-030-14812-6</isbnElectronic><issnPrint>0302-9743</issnPrint><issnElectronic>1611-3349</issnElectronic><keywords/><publishedDay>31</publishedDay><publishedMonth>12</publishedMonth><publishedYear>2019</publishedYear><publishedDate>2019-12-31</publishedDate><doi>10.1007/978-3-030-14812-6</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-04-26T15:52:23.2707948</lastEdited><Created>2019-04-08T16:22:22.1226915</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>Takayuki</firstname><surname>Kihara</surname><order>1</order></author><author><firstname>Arno</firstname><surname>Pauly</surname><orcid>0000-0002-0173-3295</orcid><order>2</order></author></authors><documents><document><filename>0049944-08042019162610.pdf</filename><originalFilename>convexchoice2-tamc.pdf</originalFilename><uploaded>2019-04-08T16:26:10.3000000</uploaded><type>Output</type><contentLength>445641</contentLength><contentType>application/pdf</contentType><version>Accepted Manuscript</version><cronfaStatus>true</cronfaStatus><embargoDate>2019-04-08T00:00:00.0000000</embargoDate><copyrightCorrect>true</copyrightCorrect><language>eng</language></document></documents><OutputDurs/></rfc1807>
spelling 2019-04-26T15:52:23.2707948 v2 49944 2019-04-08 Theory and Applications of Models of Computation 17a56a78ec04e7fc47b7fe18394d7245 0000-0002-0173-3295 Arno Pauly Arno Pauly true false 2019-04-08 SCS We study the Weihrauch degrees of closed choice for finite sets, closed choice for convex sets and sorting infinite sequences over finite alphabets. Our main result is that choice for finite sets of cardinality $i + 1$ is reducible to choice for convex sets in dimension $j$, which in turn is reducible to sorting infinite sequences over an alphabet of size $k + 1$, iff $i \leq j \leq k$. Our proofs invoke Kleene's recursion theorem, and we describe in some detail how Kleene's recursion theorem gives rise to a technique for proving separations of Weihrauch degrees. Conference Paper/Proceeding/Abstract 11436 378 15th Annual Conference, TAMC 2019, Kitakyushu, Japan, April 13–16, 2019 Japan 978-3-030-14811-9 978-3-030-14812-6 0302-9743 1611-3349 31 12 2019 2019-12-31 10.1007/978-3-030-14812-6 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2019-04-26T15:52:23.2707948 2019-04-08T16:22:22.1226915 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Takayuki Kihara 1 Arno Pauly 0000-0002-0173-3295 2 0049944-08042019162610.pdf convexchoice2-tamc.pdf 2019-04-08T16:26:10.3000000 Output 445641 application/pdf Accepted Manuscript true 2019-04-08T00:00:00.0000000 true eng
title Theory and Applications of Models of Computation
spellingShingle Theory and Applications of Models of Computation
Arno Pauly
title_short Theory and Applications of Models of Computation
title_full Theory and Applications of Models of Computation
title_fullStr Theory and Applications of Models of Computation
title_full_unstemmed Theory and Applications of Models of Computation
title_sort Theory and Applications of Models of Computation
author_id_str_mv 17a56a78ec04e7fc47b7fe18394d7245
author_id_fullname_str_mv 17a56a78ec04e7fc47b7fe18394d7245_***_Arno Pauly
author Arno Pauly
author2 Takayuki Kihara
Arno Pauly
format Conference Paper/Proceeding/Abstract
container_volume 11436
container_start_page 378
publishDate 2019
institution Swansea University
isbn 978-3-030-14811-9
978-3-030-14812-6
issn 0302-9743
1611-3349
doi_str_mv 10.1007/978-3-030-14812-6
publisher 15th Annual Conference, TAMC 2019, Kitakyushu, Japan, April 13–16, 2019
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 We study the Weihrauch degrees of closed choice for finite sets, closed choice for convex sets and sorting infinite sequences over finite alphabets. Our main result is that choice for finite sets of cardinality $i + 1$ is reducible to choice for convex sets in dimension $j$, which in turn is reducible to sorting infinite sequences over an alphabet of size $k + 1$, iff $i \leq j \leq k$. Our proofs invoke Kleene's recursion theorem, and we describe in some detail how Kleene's recursion theorem gives rise to a technique for proving separations of Weihrauch degrees.
published_date 2019-12-31T04:01:13Z
_version_ 1763753143461478400
score 11.013776

Similar Items