Solving algebraic equations using coalgebra

Federico De Marchi; Neil Ghani; Christoph Lüth[1]

  • [1] FB 3 – Mathematics and Computer Science, Universität Bremen;

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2003)

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

Abstract

top
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.

How to cite

top

Marchi, Federico De, Ghani, Neil, and Lüth, Christoph. "Solving algebraic equations using coalgebra." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 37.4 (2003): 301-314. <http://eudml.org/doc/245695>.

@article{Marchi2003,
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.},
affiliation = {FB 3 – Mathematics and Computer Science, Universität Bremen;},
author = {Marchi, Federico De, Ghani, Neil, Lüth, Christoph},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {coalgebra; recursion; category theory; algebraic system of equations; monad; locally finitely presented category; natural transformation},
language = {eng},
number = {4},
pages = {301-314},
publisher = {EDP-Sciences},
title = {Solving algebraic equations using coalgebra},
url = {http://eudml.org/doc/245695},
volume = {37},
year = {2003},
}

TY - JOUR
AU - Marchi, Federico De
AU - Ghani, Neil
AU - Lüth, Christoph
TI - Solving algebraic equations using coalgebra
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2003
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; locally finitely presented category; natural transformation
UR - http://eudml.org/doc/245695
ER -

References

top
  1. [1] 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.68077MR1976176
  2. [2] 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
  3. [3] J. Adámek, Final coalgebras are ideal completions of initial algebras. J. Log. Comput. 12 (2002) 217-242. Zbl1003.18009MR1900378
  4. [4] J. Adámek and J. Rosicky, Locally Presentable and Accessible Categories. Cambridge University Press, London Math. Soc. Lecture Notes 189 (1994). Zbl0795.18007MR1294136
  5. [5] J. Adámek, S. Milius and J. Velebil, Free iterative theories: A coalgebraic view. Math. Struct. Comput. Sci. 13 (2003) 259-320. Zbl1030.18004MR1994643
  6. [6] M. Barr, Terminal coalgebras for endofunctors on sets. Available from ftp://www.math.mcgill.ca/pub/barr/trmclgps.zip (1999). 
  7. [7] 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.68007MR496954
  8. [8] B. Courcelle, Fundamental properties of infinite trees. Theor. Comput. Sci. 25 (1983) 95-169. Zbl0521.68013MR693076
  9. [9] 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 Series 6-8, July 20–21 NS-02-2 (2002). 
  10. [10] 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
  11. [11] 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
  12. [12] I. Guessarian, Algebraic Semantics. Springer-Verlag, Lecture Notes Comput. Sci. 99 (1979). Zbl0474.68010MR617908
  13. [13] G.M. Kelly, A unified treatment of transfinite constructions. Bull. of Austral. Math. Soc. 22 (1980) 1-83. Zbl0437.18004MR589937
  14. [14] G.M. Kelly and A.J. Power, Adjunctions whose counits are equalizers, and presentations of finitary monads. J. Pure Appl. Algebra 89 (1993) 163-179. Zbl0779.18003MR1239558
  15. [15] 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
  16. [16] F. De Marchi, Monads in Coalgebra. Ph.D. thesis, Univ. of Leicester (2003) (Submitted). 
  17. [17] S. Milius, Final coalgebras in categories of monads (unpublished). 
  18. [18] 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). 
  19. [19] L. Moss, The coalgebraic treatment of second-order substitution and uniinterpreted recursive program schemes. Privately circulated manuscript. 
  20. [20] L. Moss, Parametric corecursion. Preprint, available at http://math.indiana.edu/home/moss/parametric.ps Zbl0973.68134MR1827936
  21. [21] N. Ghani and T. Uustalu, Explicit substitutions and presheafs, in Proceedings of MERLIN (2003). 
  22. [22] E. Robinson, Variations on algebra: monadicity and generalisation of equational theories. Technical Report 6/94, Sussex Computer Science (1994). Zbl1004.18005

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.