Vasco Brattka ; Arno Pauly - On the algebraic structure of Weihrauch degrees

lmcs:3854 - Logical Methods in Computer Science, October 25, 2018, Volume 14, Issue 4 - https://doi.org/10.23638/LMCS-14(4:4)2018
On the algebraic structure of Weihrauch degrees

Authors: Vasco Brattka ; Arno Pauly

    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.


    Volume: Volume 14, Issue 4
    Section: Computability and logic
    Published on: October 25, 2018
    Accepted on: October 25, 2018
    Submitted on: August 10, 2017
    Keywords: Computer Science - Logic in Computer Science,Mathematics - Logic

    Linked data

    Source : ScholeXplorer IsCitedBy DOI 10.4230/lipics.csl.2021.22
    • 10.4230/lipics.csl.2021.22
    Computing Measure as a Primitive Operation in Real Number Computation
    Ga├čner, Christine ; Pauly, Arno ; Steinberg, Florian ;

    Share

    Consultation statistics

    This page has been seen 963 times.
    This article's PDF has been downloaded 256 times.