CJO - Abstract - Monads of coalgebras: rational terms and term graphs

Cambridge Journals Online

Cambridge Journals Online
Skip to content
Mathematical Structures in Computer Science (2005), 15 : 433-451 Cambridge University Press
Copyright © 2005 Cambridge University Press
doi:10.1017/S0960129505004743 (About doi)
Published online by Cambridge University Press 27 May 2005
 
Mathematical Structures in Computer Science (2005), 15:3:433-451 Cambridge University Press
Copyright © 2005 Cambridge University Press
doi:10.1017/S0960129505004743

Paper

Monads of coalgebras: rational terms and term graphs

NEIL GHANI a1, CHRISTOPH LÜTH a2 and FEDERICO DE MARCHI a1 1
a1 Department of Mathematics and Computer Science, University of Leicester
a2 FB 3 – Mathematik und Informatik, Universität Bremen

Article author query
ghani n   [Google Scholar] 
luth c   [Google Scholar] 
de marchi f   [Google Scholar] 
 

Abstract

This paper introduces guarded and strongly guarded monads as a unified model of a variety of different term algebras covering fundamental examples such as initial algebras, final coalgebras, rational terms and term graphs. We develop a general method for obtaining finitary guarded monads that allows us to define and prove properties of the rational and term graph monads. Furthermore, our treatment of rational equations extends the traditional approach to allow right-hand sides of equations to be infinite terms, term graphs or other such coalgebraic structures. As an application, we use these generalised rational equations to sketch part of the correctness of the term graph implementation of functional programming languages.

(Received July 11 2003)


Footnotes

1 Research supported by EPSRC grant GRM96230/01: Categorical Rewriting: Monads and Modularity


back to top
Cambridge University Press