Higuchi, Kojiro and Pauly, Arno - The degree structure of Weihrauch-reducibility

lmcs:1124 - Logical Methods in Computer Science, April 2, 2013, Volume 9, Issue 2
The degree structure of Weihrauch-reducibility

Authors: Higuchi, Kojiro and Pauly, Arno

We answer a question by Vasco Brattka and Guido Gherardi by proving that the Weihrauch-lattice is not a Brouwer algebra. The computable Weihrauch-lattice is also not a Heyting algebra, but the continuous Weihrauch-lattice is. We further investigate the existence of infinite infima and suprema, as well as embeddings of the Medvedev-degrees into the Weihrauch-degrees.


Source : oai:arXiv.org:1101.0112
DOI : 10.2168/LMCS-9(2:2)2013
Volume: Volume 9, Issue 2
Published on: April 2, 2013
Submitted on: April 2, 2012
Keywords: Computer Science - Logic in Computer Science


Share

Consultation statistics

This page has been seen 45 times.
This article's PDF has been downloaded 9 times.