Presenting Distributive Laws
Distributive laws of a monad T over a functor F are categorical tools for specifying algebra-coalgebra interaction. They proved to be important for solving systems of corecursive equations, for the specification of well-behaved structural operational semantics and, more recently, also for enhancemen...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2015-08-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/1578/pdf |
| _version_ | 1811225348066508800 |
|---|---|
| author | Marcello M. Bonsangue Helle Hvid Hansen Alexander Kurz Jurriaan Rot |
| author_facet | Marcello M. Bonsangue Helle Hvid Hansen Alexander Kurz Jurriaan Rot |
| author_sort | Marcello M. Bonsangue |
| collection | DOAJ |
| description | Distributive laws of a monad T over a functor F are categorical tools for
specifying algebra-coalgebra interaction. They proved to be important for
solving systems of corecursive equations, for the specification of well-behaved
structural operational semantics and, more recently, also for enhancements of
the bisimulation proof method. If T is a free monad, then such distributive
laws correspond to simple natural transformations. However, when T is not free
it can be rather difficult to prove the defining axioms of a distributive law.
In this paper we describe how to obtain a distributive law for a monad with an
equational presentation from a distributive law for the underlying free monad.
We apply this result to show the equivalence between two different
representations of context-free languages. |
| first_indexed | 2024-04-12T09:04:27Z |
| format | Article |
| id | doaj.art-0b80e124ac7e4ebebd10a9a339dd6512 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-12T09:04:27Z |
| publishDate | 2015-08-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-0b80e124ac7e4ebebd10a9a339dd65122022-12-22T03:39:07ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742015-08-01Volume 11, Issue 310.2168/LMCS-11(3:2)20151578Presenting Distributive LawsMarcello M. Bonsanguehttps://orcid.org/0000-0003-3746-3618Helle Hvid HansenAlexander KurzJurriaan RotDistributive laws of a monad T over a functor F are categorical tools for specifying algebra-coalgebra interaction. They proved to be important for solving systems of corecursive equations, for the specification of well-behaved structural operational semantics and, more recently, also for enhancements of the bisimulation proof method. If T is a free monad, then such distributive laws correspond to simple natural transformations. However, when T is not free it can be rather difficult to prove the defining axioms of a distributive law. In this paper we describe how to obtain a distributive law for a monad with an equational presentation from a distributive law for the underlying free monad. We apply this result to show the equivalence between two different representations of context-free languages.https://lmcs.episciences.org/1578/pdfcomputer science - logic in computer science |
| spellingShingle | Marcello M. Bonsangue Helle Hvid Hansen Alexander Kurz Jurriaan Rot Presenting Distributive Laws Logical Methods in Computer Science computer science - logic in computer science |
| title | Presenting Distributive Laws |
| title_full | Presenting Distributive Laws |
| title_fullStr | Presenting Distributive Laws |
| title_full_unstemmed | Presenting Distributive Laws |
| title_short | Presenting Distributive Laws |
| title_sort | presenting distributive laws |
| topic | computer science - logic in computer science |
| url | https://lmcs.episciences.org/1578/pdf |
| work_keys_str_mv | AT marcellombonsangue presentingdistributivelaws AT hellehvidhansen presentingdistributivelaws AT alexanderkurz presentingdistributivelaws AT jurriaanrot presentingdistributivelaws |