Parlant, L;
Rot, J;
Silva, A;
Westerbaan, B;
(2020)
Preservation of Equations by Monoidal Monads.
In: Esparza, J and Král', D, (eds.)
(Proceedings) 45th MFCS 2020.
(pp. 77:1-77:1).
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Preview |
Text
LIPIcs-MFCS-2020-77.pdf - Published Version Download (5MB) | Preview |
Abstract
If a monad T is monoidal, then operations on a set X can be lifted canonically to operations on TX. In this paper we study structural properties under which T preserves equations between those operations. It has already been shown that any monoidal monad preserves linear equations; affine monads preserve drop equations (where some variable appears only on one side, such as x⋅y=y) and relevant monads preserve dup equations (where some variable is duplicated, such as x⋅x=x). We start the paper by showing a converse: if the monad at hand preserves a drop equation, then it must be affine. From this, we show that the problem whether a given (drop) equation is preserved is undecidable. A converse for relevance turns out to be more subtle: preservation of certain dup equations implies a weaker notion which we call n-relevance. Finally, we identify the subclass of equations such that their preservation is equivalent to relevance.
| Type: | Proceedings paper |
|---|---|
| Title: | Preservation of Equations by Monoidal Monads |
| Event: | 45th MFCS 2020 |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | http://arxiv.org/abs/2001.06348v2 |
| Language: | English |
| Additional information: | This work is licensed under a Creative Commons Attribution 4.0 International License. The images or other third party material in this article are included in the Creative Commons license, unless indicated otherwise in the credit line; if the material is not included under the Creative Commons license, users will need to obtain permission from the license holder to reproduce the material. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/ |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10109174 |
Archive Staff Only
 |
View Item |
