On the algebraic structure of Weihrauch degrees
arXiv:1604.08348 · doi:10.23638/LMCS-14(4:4)2018
Abstract
We introduce two new operations (compositional products and implication) on Weihrauch degrees, and investigate the overall algebraic structure. The validity of the various distributivity laws is studied and forms the basis for a comparison with similar structures such as residuated lattices and concurrent Kleene algebras. Introducing the notion of an ideal with respect to the compositional product, we can consider suitable quotients of the Weihrauch degrees. We also prove some specific characterizations using the implication. In order to introduce and study compositional products and implications, we introduce and study a function space of multi-valued continuous functions. This space turns out to be particularly well-behaved for effectively traceable spaces that are closely related to admissibly represented spaces.
References in corpus (10)
- Closed Choice and a Uniform Low Basis Theorem
- The Bolzano-Weierstrass Theorem is the Jump of Weak König's Lemma
- Probabilistic Computability and Choice
- The degree structure of Weihrauch-reducibility
- Computation with Advice
- Finite choice, convex choice and finding roots
- Connected Choice and the Brouwer Fixed Point Theorem
- Many-one reductions and the category of multivalued functions
- Point degree spectra of represented spaces
- Weak Concurrent Kleene Algebra with Application to Algebraic Verification
Cited by in corpus (15)
- Probabilistic Computability and Choice
- Weihrauch-completeness for layerwise computability
- Weihrauch goes Brouwerian
- Many-one reductions and the category of multivalued functions
- Dividing by zero - how bad is it, really?
- On the Uniform Computational Content of the Baire Category Theorem
- Projection operators in the Weihrauch lattice
- Game characterizations and lower cones in the Weihrauch degrees
- A topological view on algebraic computation models
- Convex choice, finite choice and sorting
- Borel-piecewise continuous reducibility for uniformization problems
- A comparison of various analytic choice principles
- Computability on the space of countable ordinals
- Stashing And Parallelization Pentagons
- Ramsey's theorem and products in the Weihrauch degrees