No Cover Image

Journal article 332 views 11 downloads

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

Logical Methods in Computer Science, Volume: 14, Issue: 4

Swansea University Author: Arno, Pauly

  • 39109v2.pdf

    PDF | Version of Record

    Released under the terms of a Creative Commons Attribution License (CC-BY).

    Download (622.76KB)

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 conc...

Full description

Published in: Logical Methods in Computer Science
ISSN: 1860-5974
Published: 2018
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa39109
Tags: Add Tag
No Tags, Be the first to tag this record!
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.
Keywords: Computable analysis, Weihrauch lattice, substructural logic
College: College of Science
Issue: 4