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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ita:2003021/
[1] ,, and, Infinite trees and completely iterative theories: A coalgebraic view. Theor. Comput. Sci. 300 (2003) 1-45. | MR | Zbl
[2] , and, 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).
[3] , Final coalgebras are ideal completions of initial algebras. J. Log. Comput. 12 (2002) 217-242. | MR | Zbl
[4] and, Locally Presentable and Accessible Categories. Cambridge University Press, London Math. Soc. Lecture Notes 189 (1994). | MR | Zbl
[5] , and, Free iterative theories: A coalgebraic view. Math. Struct. Comput. Sci. 13 (2003) 259-320. | MR | Zbl
[6] , Terminal coalgebras for endofunctors on sets. Available from ftp://www.math.mcgill.ca/pub/barr/trmclgps.zip (1999).
[7] , and, On the algebraic structure of rooted trees. J. Comp. Syst. Sci. 16 (1978) 361-399. | MR | Zbl
[8] , Fundamental properties of infinite trees. Theor. Comput. Sci. 25 (1983) 95-169. | MR | Zbl
[9] , and, 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] , and, Coalgebraic monads, in Proc. 5th Workshop on Coalgebraic Methods in Computer Science, edited by L.M. Moss, Grenoble, France, 6-7 April (2002).
[11] ,, and, 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).
[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] and, Adjunctions whose counits are equalizers, and presentations of finitary monads. J. Pure Appl. Algebra 89 (1993) 163-179. | MR | Zbl
[15] and, 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
[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] and, Explicit substitutions and presheafs, in Proceedings of MERLIN (2003).
[22] , Variations on algebra: monadicity and generalisation of equational theories. Technical Report 6/94, Sussex Computer Science (1994). | Zbl
Cité par Sources :
