On the algebraic structure of Weihrauch degrees
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2018-10-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/3854/pdf |
| _version_ | 1797268603079229440 |
|---|---|
| author | Vasco Brattka Arno Pauly |
| author_facet | Vasco Brattka Arno Pauly |
| author_sort | Vasco Brattka |
| collection | DOAJ |
| 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. |
| first_indexed | 2024-04-25T01:35:06Z |
| format | Article |
| id | doaj.art-fa98805099ad484db8d9994e8e9c57b0 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:35:06Z |
| publishDate | 2018-10-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-fa98805099ad484db8d9994e8e9c57b02024-03-08T10:27:52ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742018-10-01Volume 14, Issue 4Computability and logic10.23638/LMCS-14(4:4)20183854On the algebraic structure of Weihrauch degreesVasco BrattkaArno PaulyWe 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.https://lmcs.episciences.org/3854/pdfcomputer science - logic in computer sciencemathematics - logic |
| spellingShingle | Vasco Brattka Arno Pauly On the algebraic structure of Weihrauch degrees Logical Methods in Computer Science computer science - logic in computer science mathematics - logic |
| title | 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_short | On the algebraic structure of Weihrauch degrees |
| title_sort | on the algebraic structure of weihrauch degrees |
| topic | computer science - logic in computer science mathematics - logic |
| url | https://lmcs.episciences.org/3854/pdf |
| work_keys_str_mv | AT vascobrattka onthealgebraicstructureofweihrauchdegrees AT arnopauly onthealgebraicstructureofweihrauchdegrees |