Conference Paper/Proceeding/Abstract 1019 views 779 downloads
Theory and Applications of Models of Computation
Takayuki Kihara,
Arno Pauly 
Volume: 11436, Start page: 378
Swansea University Author:
Arno Pauly
-
PDF | Accepted Manuscript
Download (466.62KB)
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...
| 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 |
| 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. |
|---|---|
| College: |
Faculty of Science and Engineering |
| Start Page: |
378 |