Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-19T15:20:36.026Z Has data issue: false hasContentIssue false
  • English
  • Français

Iterative reflections of monads

Published online by Cambridge University Press:  04 February 2010

JIŘÍ ADÁMEK ,
STEFAN MILIUS  and
JIŘÍ VELEBIL
JIŘÍ ADÁMEK
Affiliation:
Institute of Theoretical Computer Science, Technical University of Braunschweig, Germany Email: [email protected], [email protected]
STEFAN MILIUS
Affiliation:
Institute of Theoretical Computer Science, Technical University of Braunschweig, Germany Email: [email protected], [email protected]
JIŘÍ VELEBIL
Affiliation:
Faculty of Electrical Engineering, Czech Technical University of Prague, Prague, Czech Republic Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Iterative monads were introduced by Calvin Elgot in the 1970's and are those ideal monads in which every guarded system of recursive equations has a unique solution. We prove that every ideal monad has an iterative reflection, that is, an embedding into an iterative monad with the expected universal property. We also introduce the concept of iterativity for algebras for the monad , following in the footsteps of Evelyn Nelson and Jerzy Tiuryn, and prove that is iterative if and only if all free algebras for are iterative algebras.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 20 , Issue 3 , June 2010 , pp. 419 - 452
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aczel, P., Adámek, J., Milius, S. and Velebil, J. (2003) Infinite trees and completely iterative theories: a coalgebraic view. Theoretical Computer Science 300 1–45.CrossRefGoogle Scholar
Adámek, J. and Milius, S. (2006) Terminal coalgebras and free iterative theories. Inform. and Comput. 204 1139–1172.CrossRefGoogle Scholar
Adámek, J., Milius, S. and Velebil, J. (2006) Iterative algebras at work. Mathematical Structures in Computer Science 16 (6)1085–1131.CrossRefGoogle Scholar
Adámek, J., Milius, S. and Velebil, J. (2009a) Semantics of higher-order recursion schemes. Proceedings CALCO 2009. Springer-Verlag Lecture Notes in Computer Science 5728 49–63.CrossRefGoogle Scholar
Adámek, J., Milius, S. and Velebil, J. (2009b) A description of iterative reflections of monads. Extended abstract in Proc. FOSSACS 2009. Springer-Verlag Lecture Notes in Computer Science 5504 152–166.CrossRefGoogle Scholar
Adámek, J. and Rosický, J. (1994) Locally presentable and accessible categories, Cambridge University Press.CrossRefGoogle Scholar
Badouel, E. (1989) Terms and infinite trees as monads over a signature. Springer-Verlag Lecture Notes in Computer Science 351 89–103.CrossRefGoogle Scholar
Barr, M. (1970) Coequalizers and free triples. Math. Z. 116 307–322.CrossRefGoogle Scholar
Bloom, S. and Ésik, Z. (1993) Iteration theories: the equational logic of iteration processes, EATCS Monographs on Theoretical Computer Science.CrossRefGoogle Scholar
Carboni, A., Lack, S. and Walters, R. F. C. (1993) Introduction to extensive and distributive categories. J. Pure Appl. Algebra 84 145–158.CrossRefGoogle Scholar
Elgot, C. C. (1975) Monadic computation and iterative algebraic theories. In: Rose, H. E. and Shepherdson, J. C. (eds.) Logic Colloquium '73, North-Holland.Google Scholar
Elgot, C. C., Bloom, S. and Tindell, R. (1978) On the algebraic structure of rooted trees. J. Comput. System Sci. 16 361–399.CrossRefGoogle Scholar
Fiore, M., Plotkin, G. and Turi, D. (1999) Abstract syntax and variable binding. Proc. Logic in Computer Science 1999, IEEE Press 193–202.CrossRefGoogle Scholar
Gabriel, P. and Ulmer, F. (1971) Lokal präsentierbare Kategorien. Springer-Verlag Lecture Notes in Mathematics 221.Google Scholar
Ginali, S. (1979) Regular Trees and the Free Iterative Theory. J. Comput. System Sci. 18 228–242.CrossRefGoogle Scholar
MacLane, S. (1998) Categories for the working mathematician, 2nd edition, Springer-Verlag.Google Scholar
Nelson, E. (1983) Iterative algebras. Theoretical Computer Science 25 67–94.CrossRefGoogle Scholar
Tiuryn, J. (1980) Unique fixed points vs. least fixed points. Theoretical Computer Science 12 229–254.CrossRefGoogle Scholar