The equational theory of the Weihrauch lattice with multiplication
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917767509180416 |
|---|---|
| author | Neumann, Eike Pauly, Arno Pradic, Cécilia |
| author_facet | Neumann, Eike Pauly, Arno Pradic, Cécilia |
| contents | We study the equational theory of the Weihrauch lattice with multiplication, meaning the collection of equations between terms built from variables, the lattice operations $\sqcup$, $\sqcap$, the product $\times$, and the finite parallelization $(-)^*$ which are true however we substitute Weihrauch degrees for the variables. We provide a combinatorial description of these in terms of a reducibility between finite graphs, and moreover, show that deciding which equations are true in this sense is complete for the third level of the polynomial hierarchy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_13975 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The equational theory of the Weihrauch lattice with multiplication Neumann, Eike Pauly, Arno Pradic, Cécilia Logic in Computer Science Logic 03D30, 08A50, 68Q17 We study the equational theory of the Weihrauch lattice with multiplication, meaning the collection of equations between terms built from variables, the lattice operations $\sqcup$, $\sqcap$, the product $\times$, and the finite parallelization $(-)^*$ which are true however we substitute Weihrauch degrees for the variables. We provide a combinatorial description of these in terms of a reducibility between finite graphs, and moreover, show that deciding which equations are true in this sense is complete for the third level of the polynomial hierarchy. |
| title | The equational theory of the Weihrauch lattice with multiplication |
| topic | Logic in Computer Science Logic 03D30, 08A50, 68Q17 |
| url | https://arxiv.org/abs/2403.13975 |