The degree structure of Weihrauch-reducibilityArticle
Authors: Kojiro Higuchi ; Arno Pauly
NULL##NULL
Kojiro Higuchi;Arno Pauly
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.
Computable Analysis; Funder: European Commission; Code: 294962
References
17 Documents citing this article
Alberto Marcone;Manlio Valenti, 2021, THE OPEN AND CLOPEN RAMSEY THEOREMS IN THE WEIHRAUCH LATTICE, arXiv (Cornell University), 86, 1, pp. 316-351, 10.1017/jsl.2021.10, https://arxiv.org/abs/2003.04245.
Takayuki Kihara;Alberto Marcone;Arno Pauly, 2020, SEARCHING FOR AN ANALOGUE OF ATR0 IN THE WEIHRAUCH LATTICE, Institutional Research Information System (University of Udine), 85, 3, pp. 1006-1043, 10.1017/jsl.2020.12, http://hdl.handle.net/11390/1204982.
Hugo Férée;Martin Ziegler, Lecture Notes in Computer Science, On the Computational Complexity of Positive Linear Functionals on $$\mathcal{C}[0;1]$$, pp. 489-504, 2016, 10.1007/978-3-319-32859-1_42.
Arno Pauly;Matthew de Brecht, 2014, Non-deterministic computation and the Jayne-Rogers Theorem, arXiv (Cornell University), 143, pp. 87-96, 10.4204/eptcs.143.8.