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.
Mots-clés : coalgebra, recursion, category theory
@article{ITA_2003__37_4_301_0, author = {Marchi, Federico De and Ghani, Neil and L\"uth, Christoph}, title = {Solving algebraic equations using coalgebra}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {301--314}, publisher = {EDP-Sciences}, volume = {37}, number = {4}, year = {2003}, doi = {10.1051/ita:2003021}, mrnumber = {2053029}, zbl = {1038.18005}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita:2003021/} }
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 SP - 301 EP - 314 VL - 37 IS - 4 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita:2003021/ DO - 10.1051/ita:2003021 LA - en ID - ITA_2003__37_4_301_0 ER -
%0 Journal Article %A Marchi, Federico De %A Ghani, Neil %A Lüth, Christoph %T Solving algebraic equations using coalgebra %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2003 %P 301-314 %V 37 %N 4 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita:2003021/ %R 10.1051/ita:2003021 %G en %F ITA_2003__37_4_301_0
Marchi, Federico De; Ghani, Neil; Lüth, Christoph. Solving algebraic equations using coalgebra. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 4, pp. 301-314. doi : 10.1051/ita:2003021. http://archive.numdam.org/articles/10.1051/ita:2003021/
[1] Infinite trees and completely iterative theories: A coalgebraic view. Theor. Comput. Sci. 300 (2003) 1-45. | MR | Zbl
, , and ,[2] 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).
, and ,[3] Final coalgebras are ideal completions of initial algebras. J. Log. Comput. 12 (2002) 217-242. | MR | Zbl
,[4] Locally Presentable and Accessible Categories. Cambridge University Press, London Math. Soc. Lecture Notes 189 (1994). | MR | Zbl
and ,[5] Free iterative theories: A coalgebraic view. Math. Struct. Comput. Sci. 13 (2003) 259-320. | MR | Zbl
, and ,[6] Terminal coalgebras for endofunctors on sets. Available from ftp://www.math.mcgill.ca/pub/barr/trmclgps.zip (1999).
,[7] On the algebraic structure of rooted trees. J. Comp. Syst. Sci. 16 (1978) 361-399. | MR | Zbl
, and ,[8] Fundamental properties of infinite trees. Theor. Comput. Sci. 25 (1983) 95-169. | MR | Zbl
,[9] 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).
, and ,[10] Coalgebraic monads, in Proc. 5th Workshop on Coalgebraic Methods in Computer Science, edited by L.M. Moss, Grenoble, France, 6-7 April (2002).
, and ,[11] 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).
, , and ,[12] Algebraic Semantics. Springer-Verlag, Lecture Notes Comput. Sci. 99 (1979). | MR | Zbl
,[13] A unified treatment of transfinite constructions. Bull. of Austral. Math. Soc. 22 (1980) 1-83. | MR | Zbl
,[14] Adjunctions whose counits are equalizers, and presentations of finitary monads. J. Pure Appl. Algebra 89 (1993) 163-179. | MR | Zbl
and ,[15] 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). | Zbl
and ,[16] Monads in Coalgebra. Ph.D. thesis, Univ. of Leicester (2003) (Submitted).
,[17] Final coalgebras in categories of monads (unpublished).
,[18] Free iterative theories: a coalgebraic view (extended abstract), presented at FICS 2001 - Fixed Points in Computer Science, 7-8 September, Florence, Italy (2001).
,[19] The coalgebraic treatment of second-order substitution and uniinterpreted recursive program schemes. Privately circulated manuscript.
,[20] Parametric corecursion. Preprint, available at http://math.indiana.edu/home/moss/parametric.ps | MR | Zbl
,[21] Explicit substitutions and presheafs, in Proceedings of MERLIN (2003).
and ,[22] Variations on algebra: monadicity and generalisation of equational theories. Technical Report 6/94, Sussex Computer Science (1994). | Zbl
,Cité par Sources :