No Cover Image

Journal article 1389 views 84 downloads

On the algebraic structure of Weihrauch degrees

Vasco Brattka, Arno Pauly Orcid Logo

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

Swansea University Author: Arno Pauly Orcid Logo

  • 39109v2.pdf

    PDF | Version of Record

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

    Download (622.76KB)

Check full text

DOI (Published version): 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 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
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>MACS</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>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</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">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - 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 MACS 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 Mathematics and Computer Science School COLLEGE CODE MACS Swansea University 2018-11-08T17:07:44.7901961 2018-03-20T16:21:08.8834416 Faculty of Science and Engineering School of Mathematics and Computer 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 Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer 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-25T04:26:12Z
_version_ 1821378160766222336
score 11.04748

Similar Items