The degree structure of Weihrauch-reducibility

Kojiro Higuchi; Arno Pauly

doi:10.2168/LMCS-9(2:2)2013

Kojiro Higuchi ; Arno Pauly - The degree structure of Weihrauch-reducibility

lmcs:1124 - Logical Methods in Computer Science, April 2, 2013, Volume 9, Issue 2 - https://doi.org/10.2168/LMCS-9(2:2)2013

The degree structure of Weihrauch-reducibilityArticle

Authors: 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.

https://doi.org/10.2168/LMCS-9(2:2)2013

Source: arXiv.org:1101.0112

Volume: Volume 9, Issue 2

Published on: April 2, 2013

Imported on: April 2, 2012

Keywords: Computer Science - Logic in Computer Science

Licence: arXiv.org - Non-exclusive license to distribute

Funding:

Source : OpenAIRE Graph

Computable Analysis; Funder: European Commission; Code: 294962

Classifications

Mathematics Subject Classification 2020¹

Sources:

[1] zbMATH Open.

Publications

Has review

Review available on zbMATH Open, by Martin W. Bunder (Wollongong) (English)

1 zbMATH Open

Bibliographic References

20 Documents citing this article

Arno Pauly;Giovanni Soldà, 2024, Sequential Discontinuity and First-Order Problems, Lecture notes in computer science, pp. 351-365, 10.1007/978-3-031-64309-5_28.

Patrick Uftring, 2024, Weihrauch degrees without roots, Computability, 14, 1, pp. 17-29, 10.3233/com-230471.

Steffen Lempp;Joseph Miller;Arno Pauly;Mariya Soskova;Manlio Valenti, 2024, Minimal covers in the Weihrauch degrees, Cronfa (Swansea University), 152, 11, pp. 4893-4901, 10.1090/proc/16952, https://cronfa.swan.ac.uk/Record/cronfa66479.

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, http://arxiv.org/abs/1812.01549.

Damir D. Dzhafarov;Jun Le Goh;Denis R. Hirschfeldt;Ludovic Patey;Arno Pauly, 2020, Ramsey’s theorem and products in the Weihrauch degrees, 9, 2, pp. 85-110, 10.3233/com-180203, https://hal.science/hal-01888805.

Jun Le Goh, 2020, Compositions of multivalued functions, Computability, 9, 3-4, pp. 231-247, 10.3233/com-180235.

TAKAYUKI KIHARA;ALBERTO MARCONE;ARNO PAULY, 2020, SEARCHING FOR AN ANALOGUE OF ATR0 IN THE WEIHRAUCH LATTICE, Journal of Symbolic Logic, 85, 3, pp. 1006-1043, 10.1017/jsl.2020.12, https://doi.org/10.1017/jsl.2020.12.

VASCO BRATTKA;GUIDO GHERARDI, 2020, WEIHRAUCH GOES BROUWERIAN, arXiv (Cornell University), 85, 4, pp. 1614-1653, 10.1017/jsl.2020.76, http://arxiv.org/abs/1809.00380.

Eike Neumann;Arno Pauly, 2017, A topological view on algebraic computation models, Journal of Complexity, 44, pp. 1-22, 10.1016/j.jco.2017.08.003.

Hugo Nobrega;Arno Pauly, 2017, Game Characterizations and Lower Cones in the Weihrauch Degrees, Cronfa (Swansea University), pp. 327-337, 10.1007/978-3-319-58741-7_31.

Vasco Brattka;Matthew Hendtlass;Alexander P. Kreuzer, 2017, On the Uniform Computational Content of Computability Theory, arXiv (Cornell University), 61, 4, pp. 1376-1426, 10.1007/s00224-017-9798-1, http://arxiv.org/abs/1501.00433.

Hugo Férée;Martin Ziegler, 2016, On the Computational Complexity of Positive Linear Functionals on $$\mathcal{C}[0;1]$$, Lecture notes in computer science, pp. 489-504, 10.1007/978-3-319-32859-1_42.

Vasco Brattka;Stéphane Le Roux;Joseph S. Miller;Arno Pauly, 2016, The Brouwer Fixed Point Theorem Revisited, Lecture notes in computer science, pp. 58-67, 10.1007/978-3-319-40189-8_6.

ARNO PAULY, 2015, Many-one reductions and the category of multivalued functions, arXiv (Cornell University), 27, 3, pp. 376-404, 10.1017/s0960129515000262, http://arxiv.org/abs/1102.3151.

Arno Pauly, 2015, Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract), Lecture notes in computer science, pp. 407-418, 10.1007/978-3-662-48057-1_32.

Akitoshi Kawamura;Arno Pauly, 2014, Function Spaces for Second-Order Polynomial Time, Cronfa (Swansea University), pp. 245-254, 10.1007/978-3-319-08019-2_25.

Arno Pauly;Matthew de Brecht, 2014, Non-deterministic computation and the Jayne-Rogers Theorem, Electronic Proceedings in Theoretical Computer Science, 143, pp. 87-96, 10.4204/eptcs.143.8, https://doi.org/10.4204/eptcs.143.8.

K. Higuchi;T. Kihara, 2014, Inside the Muchnik degrees I: Discontinuity, learnability and constructivism, Annals of Pure and Applied Logic, 165, 5, pp. 1058-1114, 10.1016/j.apal.2014.01.003.

Xiang Jiang;Arno Pauly, 2014, Efficient Decomposition of Bimatrix Games (Extended Abstract), Electronic Proceedings in Theoretical Computer Science, 146, pp. 75-81, 10.4204/eptcs.146.10, https://doi.org/10.4204/eptcs.146.10.

Stéphane Le Roux;Arno Pauly, 2013, Closed Choice for Finite and for Convex Sets, Lecture notes in computer science, pp. 294-305, 10.1007/978-3-642-39053-1_34.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 3372 times.

This article's PDF has been downloaded 670 times.