Dexter Kozen - Natural Transformations as Rewrite Rules and Monad Composition

lmcs:2609 - Logical Methods in Computer Science, January 9, 2019, Volume 15, Issue 1 - https://doi.org/10.23638/LMCS-15(1:1)2019
Natural Transformations as Rewrite Rules and Monad CompositionArticle

Authors: Dexter Kozen

Eklund et al. (2002) present a graphical technique aimed at simplifying the verification of various category-theoretic constructions, notably the composition of monads. In this note we take a different approach involving string rewriting. We show that a given tuple $(T,\mu,\eta)$ is a monad if and only if $T$ is a terminal object in a certain category of strings and rewrite rules, and that this fact can be established by proving confluence of the rewrite system. We illustrate the technique on the monad composition problem.
We also give a characterization of adjunctions in terms of rewrite categories.


Volume: Volume 15, Issue 1
Secondary volumes: Special Festschrift Issue in Honor of Jiří Adámek
Published on: January 9, 2019
Accepted on: September 7, 2018
Submitted on: December 22, 2016
Keywords: Computer Science - Logic in Computer Science

1 Document citing this article

Consultation statistics

This page has been seen 2870 times.
This article's PDF has been downloaded 877 times.