# Solving Algebraic Equations Using Coalgebra

Federico De Marchi; Neil Ghani; Christoph Lüth

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 37, Issue: 4, page 301-314
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topDe Marchi, Federico, Ghani, Neil, and Lüth, Christoph. "Solving Algebraic Equations Using Coalgebra." RAIRO - Theoretical Informatics and Applications 37.4 (2010): 301-314. <http://eudml.org/doc/92725>.

@article{DeMarchi2010,

abstract = {
Algebraic systems of equations define functions using recursion
where parameter passing is permitted. This generalizes the
notion of a rational system of equations where parameter passing is
prohibited. It has been known for some time that algebraic systems
in Greibach Normal Form have unique solutions. This paper presents a categorical approach to algebraic systems of
equations which generalizes the traditional approach in two ways i)
we define algebraic equations for locally finitely presentable
categories rather than just Set; and ii) we define algebraic
equations to allow right-hand sides which need not consist of finite
terms. We show these generalized algebraic systems of equations have
unique solutions by replacing the traditional metric-theoretic
arguments with coalgebraic arguments.
},

author = {De Marchi, Federico, Ghani, Neil, Lüth, Christoph},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Coalgebra; recursion; category theory.; algebraic system of equations; monad; coalgebra; locally finitely presented category; natural transformation},

language = {eng},

month = {3},

number = {4},

pages = {301-314},

publisher = {EDP Sciences},

title = {Solving Algebraic Equations Using Coalgebra},

url = {http://eudml.org/doc/92725},

volume = {37},

year = {2010},

}

TY - JOUR

AU - De Marchi, Federico

AU - Ghani, Neil

AU - Lüth, Christoph

TI - Solving Algebraic Equations Using Coalgebra

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 37

IS - 4

SP - 301

EP - 314

AB -
Algebraic systems of equations define functions using recursion
where parameter passing is permitted. This generalizes the
notion of a rational system of equations where parameter passing is
prohibited. It has been known for some time that algebraic systems
in Greibach Normal Form have unique solutions. This paper presents a categorical approach to algebraic systems of
equations which generalizes the traditional approach in two ways i)
we define algebraic equations for locally finitely presentable
categories rather than just Set; and ii) we define algebraic
equations to allow right-hand sides which need not consist of finite
terms. We show these generalized algebraic systems of equations have
unique solutions by replacing the traditional metric-theoretic
arguments with coalgebraic arguments.

LA - eng

KW - Coalgebra; recursion; category theory.; algebraic system of equations; monad; coalgebra; locally finitely presented category; natural transformation

UR - http://eudml.org/doc/92725

ER -

## References

top- P. Aczel, J. Adámek, S. Milius and J. Velebil, Infinite trees and completely iterative theories: A coalgebraic view. Theor. Comput. Sci.300 (2003) 1-45 . Zbl1028.68077
- P. Aczel, J. Adámek and J. Velebil, A coalgebraic view of infinite trees and iteration, in Proceedings 4th Workshop on Coalgebraic Methods in Computer Science, CMCS'01, edited by A. Corradini, M. Lenisa and U. Montanari, Genova, Italy, 6-7 April 2001. Elsevier, Electronics Notes Theor. Comput. Sci.44 (2001). Zbl1260.68235
- J. Adámek, Final coalgebras are ideal completions of initial algebras. J. Log. Comput.12 (2002) 217-242. Zbl1003.18009
- J. Adámek and J. Rosicky, Locally Presentable and Accessible Categories. Cambridge University Press, London Math. Soc. Lecture Notes189 (1994). Zbl0795.18007
- J. Adámek, S. Milius and J. Velebil, Free iterative theories: A coalgebraic view. Math. Struct. Comput. Sci.13 (2003) 259-320. Zbl1030.18004
- M. Barr, Terminal coalgebras for endofunctors on sets. Available from (1999).
- C.C. Elgot, S.L. Bloom and S. Tindell, On the algebraic structure of rooted trees. J. Comp. Syst. Sci.16 (1978) 361-399. Zbl0389.68007
- B. Courcelle, Fundamental properties of infinite trees. Theor. Comput. Sci.25 (1983) 95-169 . Zbl0521.68013
- N. Ghani, C. Lüth and F. De Marchi, Coalgebraic approaches to algebraic terms, in Fixed Points in Computer Science, edited by Z. Ésik and A. Ingólfsdóttir. BRICS Notes Series6-8, July 20-21 NS-02-2 (2002).
- N. Ghani, C. Lüth and F. De Marchi, Coalgebraic monads, in Proc. 5th Workshop on Coalgebraic Methods in Computer Science, edited by L.M. Moss, Grenoble, France, 6-7 April (2002). Zbl1270.18011
- N. Ghani, C. Lüth, F. De Marchi and J. Power, Algebras, coalgebras, monads and comonads, in Proceedings 4th Workshop on Coalgebraic Methods in Computer Science, edited by A. Corradini, M. Lenisa and U. Montanari, Genova, Italy, 6-7 April 2001. Elsevier, Electronics Notes Theor. Comput. Sci.44 (2001). Zbl1260.68238
- I. Guessarian, Algebraic Semantics. Springer-Verlag, Lecture Notes Comput. Sci.99 (1979). Zbl0399.68023
- G.M. Kelly, A unified treatment of transfinite constructions. Bull. of Austral. Math. Soc.22 (1980) 1-83.
- G.M. Kelly and A.J. Power, Adjunctions whose counits are equalizers, and presentations of finitary monads. J. Pure Appl. Algebra89 (1993) 163-179 . Zbl0779.18003
- C. Lüth and N. Ghani, Monads and modular term rewriting, in Proc. 7th Int. Conf. on Category Theory and Computer Science, edited by E. Moggi and G. Rosolini, Santa Margherita Ligure, Italy, 4-6 September 1997. Springer-Verlag, Lecture Notes Comput. Sci.1290 69-86 (1997). Zbl0889.68084
- F. De Marchi, Monads in Coalgebra. Ph.D. thesis, Univ. of Leicester (2003) (Submitted).
- S. Milius, Final coalgebras in categories of monads (unpublished).
- S. Milius, Free iterative theories: a coalgebraic view (extended abstract), presented at FICS 2001 - Fixed Points in Computer Science, 7-8 September, Florence, Italy (2001).
- L. Moss, The coalgebraic treatment of second-order substitution and uniinterpreted recursive program schemes. Privately circulated manuscript.
- L. Moss, Parametric corecursion. Preprint, available at Zbl0973.68134URIhttp://math.indiana.edu/home/moss/parametric.ps
- N. Ghani and T. Uustalu, Explicit substitutions and presheafs, in Proceedings of MERLIN (2003).
- E. Robinson, Variations on algebra: monadicity and generalisation of equational theories. Technical Report 6/94, Sussex Computer Science (1994).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.