No Cover Image

Conference contribution 22 views 3 downloads

Theory and Applications of Models of Computation / Takayuki Kihara; Arno Pauly

Volume: 11436, Start page: 378

Swansea University Author: Pauly, Arno

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!
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: College of Science
Start Page: 378