A coalgebraic view of infinite trees and iteration. (English) Zbl 1260.68235
Corradini, Andrea (ed.) et al., CMCS 2001. Proceedings of the 4th workshop on coalgebraic methods in computer science, Genova, Italy, April 6–7, 2001. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 44, No. 1, 1-26 (2001).
Summary: The algebra of infinite trees is, as proved by C. Elgot, completely iterative, i.e., all ideal recursive equations are uniquely solvable. This is proved here to be a general coalgebraic phenomenon: let \(H\) be an endofunctor such that for every object \(X\) a final coalgebra, \(TX\), of \(H(\_)+ X\) exists. Then \(TX\) is an object-part of a monad which is completely iterative. Moreover, a similar contruction of a “completely iterative monoid” is possible in every monoidal category satisfying mild side conditions.
For the entire collection see [Zbl 1260.68011].
For the entire collection see [Zbl 1260.68011].
MSC:
| 68Q65 | Abstract data types; algebraic specification |
| 18C15 | Monads (= standard construction, triple or triad), algebras for monads, homology and derived functors for monads |
| 18D10 | Monoidal, symmetric monoidal and braided categories (MSC2010) |
References:
| [1] | Aczel, P., “Non-Well-Founded Sets” (1988), CSLI Publications: CSLI Publications Stanford · Zbl 0668.04001 |
| [2] | Adámek, J., Free Algebras and Automata Realizations in the Language of Categories, Comment. Math. Univ. Carolinae, 15, 589-602 (1974) · Zbl 0293.18006 |
| [3] | Adámek, J.; Koubek, V., On the Greatest Fixed Point of a Set Functor, Theor. Comp. Science, 150, 57-75 (1995) · Zbl 0874.18001 |
| [4] | Adámek, J.; Trnková, V., “Automata and Algebras in Categories,” (1990), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0698.18001 |
| [5] | Adámek, J.; Rosický, J., “Locally presentable and accessible categories” (1994), Cambridge University Press · Zbl 0795.18007 |
| [6] | America, P.; Rutten, J., Solving Reflexive Domain Equations in a Category of Complete Metric Spaces, J. Comp. System Sci, 39, 343-375 (1989) · Zbl 0717.18002 |
| [7] | Goguen, J. A., S. W. Thatcher, E. G. Wagner and J. B. Wright, Initial Algebra Semantics and Continuous Algebras; Goguen, J. A., S. W. Thatcher, E. G. Wagner and J. B. Wright, Initial Algebra Semantics and Continuous Algebras · Zbl 0359.68018 |
| [8] | Barr, M., Terminal Coalgebras in Well-founded Set Theory, Theor. Comp. Science, 114, 299-315 (1993) · Zbl 0779.18004 |
| [9] | Barwise, J.; Etchemendy, J., “The Liar: An Essay in Truth and Circularity” (1987), Oxford University Press · Zbl 0678.03001 |
| [10] | Barwise, J.; Moss, L., “Vicious Circles” (1996), CSLI Publications: CSLI Publications Stanford · Zbl 0865.03002 |
| [11] | Elgot, C. C., Monadic Computation and Iterative Algebraic Theories, (Rose, H. E.; Shepherdson, J. C., “Logic Colloquium ‘73” (1975), North-Holland Publishers: North-Holland Publishers Amsterdam) · Zbl 0327.02040 |
| [12] | Kozen, D., A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events, Inform. and Comput, 110, 366-390 (1994) · Zbl 0806.68082 |
| [13] | Lambek, J., A Fixpoint Theorem for Complete Categories, Mathematische Zeitschrift, 103, 151-161 (1968) · Zbl 0149.26105 |
| [14] | Linton, F. E.J., Some aspects of equational categories, (“Proc. Conf. Categorical Algebra, La Jolla 1965” (1966), Springer-Verlag), 84-94 · Zbl 0201.35003 |
| [15] | Moss L., Parametric Corecursionhttp://math.indiana.edu/home/moss/parametric.ps; Moss L., Parametric Corecursionhttp://math.indiana.edu/home/moss/parametric.ps · Zbl 0973.68134 |
| [16] | Moss L., Recursion and Corecursion Have the Same Equational Logichttp://math.indiana.edu/home/moss/eqcoeq.ps; Moss L., Recursion and Corecursion Have the Same Equational Logichttp://math.indiana.edu/home/moss/eqcoeq.ps · Zbl 0924.68114 |
| [17] | Smyth, M. B.; Plotkin, G. D., The Category-theoretic Solution of Recursive Domain Equations, SIAM J. Comput, 11, 761-783 (1982) · Zbl 0493.68022 |
| [18] | Tiurin, J., Unique Fixed Points vs. Least Fixed Points, Theoretical Computer Science, 12, 229-254 (1980) · Zbl 0439.68026 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
