No Cover Image

Journal article 446 views 18 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!
first_indexed 2018-03-20T20:34:30Z
last_indexed 2018-11-10T05:07:15Z
id cronfa39109
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2018-11-08T17:07:44.7901961</datestamp><bib-version>v2</bib-version><id>39109</id><entry>2018-03-20</entry><title>On the algebraic structure of Weihrauch degrees</title><swanseaauthors><author><sid>17a56a78ec04e7fc47b7fe18394d7245</sid><ORCID>0000-0002-0173-3295</ORCID><firstname>Arno</firstname><surname>Pauly</surname><name>Arno Pauly</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2018-03-20</date><deptcode>SCS</deptcode><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 speci&#xFB01;c 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 e&#xFB00;ectively traceable spaces that are closely related to admissibly represented spaces.</abstract><type>Journal Article</type><journal>Logical Methods in Computer Science</journal><volume>14</volume><journalNumber>4</journalNumber><publisher/><issnElectronic>1860-5974</issnElectronic><keywords>Computable analysis, Weihrauch lattice, substructural logic</keywords><publishedDay>25</publishedDay><publishedMonth>10</publishedMonth><publishedYear>2018</publishedYear><publishedDate>2018-10-25</publishedDate><doi>10.23638/LMCS-14(4:4)2018</doi><url>https://lmcs.episciences.org/4918</url><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><lastEdited>2018-11-08T17:07:44.7901961</lastEdited><Created>2018-03-20T16:21:08.8834416</Created><path><level id="1">College of Science</level><level id="2">Computer Science</level></path><authors><author><firstname>Vasco</firstname><surname>Brattka</surname><order>1</order></author><author><firstname>Arno</firstname><surname>Pauly</surname><orcid>0000-0002-0173-3295</orcid><order>2</order></author></authors><documents><document><filename>0039109-08112018170701.pdf</filename><originalFilename>39109v2.pdf</originalFilename><uploaded>2018-11-08T17:07:01.5970000</uploaded><type>Output</type><contentLength>588433</contentLength><contentType>application/pdf</contentType><version>Version of Record</version><cronfaStatus>true</cronfaStatus><embargoDate>2018-11-07T00:00:00.0000000</embargoDate><documentNotes>Released under the terms of a Creative Commons Attribution License (CC-BY).</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language></document></documents><OutputDurs/></rfc1807>
spelling 2018-11-08T17:07:44.7901961 v2 39109 2018-03-20 On the algebraic structure of Weihrauch degrees 17a56a78ec04e7fc47b7fe18394d7245 0000-0002-0173-3295 Arno Pauly Arno Pauly true false 2018-03-20 SCS 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. Journal Article Logical Methods in Computer Science 14 4 1860-5974 Computable analysis, Weihrauch lattice, substructural logic 25 10 2018 2018-10-25 10.23638/LMCS-14(4:4)2018 https://lmcs.episciences.org/4918 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2018-11-08T17:07:44.7901961 2018-03-20T16:21:08.8834416 College of Science Computer Science Vasco Brattka 1 Arno Pauly 0000-0002-0173-3295 2 0039109-08112018170701.pdf 39109v2.pdf 2018-11-08T17:07:01.5970000 Output 588433 application/pdf Version of Record true 2018-11-07T00:00:00.0000000 Released under the terms of a Creative Commons Attribution License (CC-BY). true eng
title On the algebraic structure of Weihrauch degrees
spellingShingle On the algebraic structure of Weihrauch degrees
Arno, Pauly
title_short On the algebraic structure of Weihrauch degrees
title_full On the algebraic structure of Weihrauch degrees
title_fullStr On the algebraic structure of Weihrauch degrees
title_full_unstemmed On the algebraic structure of Weihrauch degrees
title_sort On the algebraic structure of Weihrauch degrees
author_id_str_mv 17a56a78ec04e7fc47b7fe18394d7245
author_id_fullname_str_mv 17a56a78ec04e7fc47b7fe18394d7245_***_Arno, Pauly
author Arno, Pauly
author2 Vasco Brattka
Arno Pauly
format Journal article
container_title Logical Methods in Computer Science
container_volume 14
container_issue 4
publishDate 2018
institution Swansea University
issn 1860-5974
doi_str_mv 10.23638/LMCS-14(4:4)2018
college_str College of Science
hierarchytype
hierarchy_top_id collegeofscience
hierarchy_top_title College of Science
hierarchy_parent_id collegeofscience
hierarchy_parent_title College of Science
department_str Computer Science{{{_:::_}}}College of Science{{{_:::_}}}Computer Science
url https://lmcs.episciences.org/4918
document_store_str 1
active_str 0
description 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.
published_date 2018-10-25T03:54:47Z
_version_ 1717733255222919168
score 10.842861