On the algebraic structure of Weihrauch degrees

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 (2)

• Computation with Advice
• Weak Concurrent Kleene Algebra with Application to Algebraic Verification

Cited by in corpus (13)

• Weihrauch-completeness for layerwise computability
• Weihrauch goes Brouwerian
• 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
• Computability on the space of countable ordinals
• Borel-piecewise continuous reducibility for uniformization problems
• A comparison of various analytic choice principles
• Stashing And Parallelization Pentagons
• Ramsey's theorem and products in the Weihrauch degrees