Skip Navigation


Journal of Logic and Computation Advance Access originally published online on October 1, 2008
Journal of Logic and Computation 2008 18(6):1047-1085; doi:10.1093/logcom/exn035
This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Adámek, J.
Right arrow Articles by Milius, S.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2008. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Original Articles

On Algebras with Iteration

Jirí Adámek

Technical University of Braunschweig, Germany.
E-mail: adamek{at}iti.cs.tu-bs.de

Stephen L. Bloom

Stevens Institute of Technology, Hoboken (NJ), USA.

Stefan Milius

Technical University of Braunschweig, Germany.

Received 15 March 2007.

Several concepts of algebras with solutions of recursive equation systems are compared: CPO-enrichable algebras are proved to be iteration algebras of Z. Ésik, and iteration algebras are a special case of the recently introduced Elgot algebras (which are the monadic algebras for the free iterative monad). Another special case of iteration algebras are the iterative algebras of E. Nelson and J. Tiuryn, which are algebras with unique solutions of all guarded systems. For each of the above classes of algebras an example is provided showing that the inclusion in a wider class is proper.



References

  1. Aczel P, Adámek J, Milius S, Velebil J. Infinite trees and completely iterative algebras, a coalgebraic view. Theoretical Computer Science (2003) 300:1–45.[CrossRef][Web of Science]
  2. Adámek J. Free algebras and automata realizations in the language of categories. Comment. Math. Univ. Carolinæ (1974) 15:589–602.
  3. Adámek J. On final coalgebras of continuous functors. Theoretical Computer Science (2003) 294:3–29.[CrossRef][Web of Science]
  4. Adámek J, Börger R, Milius S, Velebil J. Iterative algebras: how iterative are they? Theory and Applications of Categories (2008) 19:61–92.
  5. Adámek J, Koubek V. On the greatest fixed point of a set functor. Theoretical Computer Science (1995) 150:57–75.[CrossRef][Web of Science]
  6. Adámek J, Milius S. Terminal coalgebras and free iterative theories. Information and Computation (2006) 204:1139–1172.[CrossRef][Web of Science]
  7. Adámek J, Milius S, Velebil J. On rational monads and free iterative theories. Electron. Notes Theoret. Comput. Sci (2002) 69.
  8. Adámek J, Milius S, Velebil J. Elgot algebras. Logical Methods in Computer Science (2006) 2:1–31.
  9. Adámek J, Milius S, Velebil J. Equational properties of iteration theories (a manuscript).
  10. Adámek J, Milius S, Velebil J. Iterative algebras at work. Mathematical Structures in Computer Science (2006) 16:1085–1131.[CrossRef][Web of Science]
  11. Adámek J, Porst H-E. On tree coalgebras and coalgebra presentations. Theoretical Computer Science (2004) 311:257–283.[CrossRef][Web of Science]
  12. Adámek J, Rosicky J. Locally Presentable and Accessible Categories (1994) Cambridge University Press.
  13. America P, Rutten JJMM. Solving reflexive domain equations in a category of complete metric spaces. Journal of Computer and System Sciences (1989) 39:343–375.[CrossRef][Web of Science]
  14. Bloom SL, Elgot CC, Wright JB. Solutions of the iteration equation and extensions of the scalar iteration operation. SIAM Journal of Computing (1980) 9:25–45.[CrossRef]
  15. Bloom SL, Ésik Z. Iteration Theories: The Equational Logic of Iterative Processes (1993) Sringer-Verlag.
  16. Carboni A, Lack S, Walters RFC. Introduction to extensive and distributive categories. Journal of Pure and Applied Algebra (1993) 84:145–158.[CrossRef][Web of Science]
  17. Elgot CC. Monadic computation and iterative algebraic theories. In. In: Logic Colloquium 1973, Studies in Logic—Shepherdson JC, ed. (1975) 80.
  18. Elgot CC, Bloom SL, Tindell R. On the algebraic structure of rooted trees. Journal of Computer and System Sciences (1978) 16:362–399.[CrossRef][Web of Science]
  19. Ésik Z. Algebras of iteration theories. Journal of Computer and System Sciences (1983) 27:291–303.[CrossRef][Web of Science]
  20. Gabriel P, Ulmer F. Lokal präsentierbare Kategorien (1971) Berlin: Springer-Verlag. Vol. 221 of Lecture Notes in Mathematics.
  21. Milius S. Completely iterative algebras and completely iterative monads. Information and Computing (2005) 196:1–41.[CrossRef]
  22. Milius S, Moss LS. The category-theoretic solution of recursive program schemes. Theoretical Computer Science (2006) 366:3–59.[CrossRef][Web of Science]
  23. Moss LS. Recursion and corecursion have the same equational logic. Theoretical Computer Science (2003) 294:233–267.[CrossRef][Web of Science]
  24. Nelson E. Iterative algebras. Theoretical Computer Science (1983) 25:67–94.[CrossRef][Web of Science]
  25. Tiuryn J. Unique fixed points and least fixed points. Theoretical Computer Science (1980) 12:229–254.[CrossRef][Web of Science]
  26. Wechler W. Universal Algebra for Computer Scientists (1992) Springer-Verlag.

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Adámek, J.
Right arrow Articles by Milius, S.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?