Document Open Access Logo

On Corecursive Algebras for Functors Preserving Coproducts

Authors Jiri Adámek, Stefan Milius

PDF
Thumbnail PDF

File

LIPIcs.CALCO.2017.3.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Author Details

Jiri Adámek
Stefan Milius

Cite As Get BibTex

Jiri Adámek and Stefan Milius. On Corecursive Algebras for Functors Preserving Coproducts. In 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 72, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CALCO.2017.3

Abstract

For an endofunctor H on a hyper-extensive category preserving countable coproducts we describe the free corecursive algebra on Y as the coproduct of the terminal coalgebra for H and the free H-algebra on Y. As a consequence, we derive that H is a cia functor, i.e., its corecursive algebras are precisely the cias (completely iterative algebras). Also all functors H(-) + Y are then cia functors.  For finitary set functors we prove that, conversely, if H is a cia functor, then it has the form H = W \times (-) + Y for some sets W and Y.

Subject Classification

Keywords
  • terminal coalgebra
  • free algebra
  • corecursive algebra
  • hyper-extensive category

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Peter Aczel, Jiří Adámek, Stefan Milius, and Jiří Velebil. Infinite trees and completely iterative theories: A coalgebraic view. Theoret. Comput. Sci., 300:1-45, 2003. Fundamental study. Google Scholar
  2. Jiří Adámek, Reinhard Börger, Stefan Milius, and Jiří Velebil. Iterative algebras: How iterative are they? Theory Appl. Categ., 19:61-92, 2008. Google Scholar
  3. Jiří Adámek, Mahdieh Haddadi, and Stefan Milius. Corecursive algebras, corecursive monads and Bloom monads. Log. Methods Comput. Sci., 10(3:19):51 pp., 2014. Google Scholar
  4. Jiří Adámek and Stefan Milius. Terminal coalgebras and free iterative theories. Inform. and Comput., 204:1139-1172, 2006. Google Scholar
  5. Jiří Adámek and Stefan Milius. On corecursive algebras for functors preserving coproducts. full version, 2017. URL: https://arxiv.org/abs/1703.07574.
  6. Jiří Adámek and Hans-Eberhard Porst. On tree coalgebras and coalgebra presentations. Theoret. Comput. Sci., 311:257-283, 2004. Google Scholar
  7. Jiří Adámek and Věra Trnková. Automata and Algebras in Categories, volume 37 of Mathematics and its Applications. Kluwer Academic Publishers, 1990. Google Scholar
  8. Michael A. Arbib and Ernest G. Manes. Foundations of system theory: Decomposable systems. Automatica, 10:285-302, 1974. Google Scholar
  9. Venanzio Capretta, Tarmo Uustalu, and Varmo Vene. Corecusive algebras: A study of general structured corecursion. In M. V. M. Oliveira and J. Woodcock, editors, Proc. Brazilian Symposium on Formal Methods (SBMF'09), volume 5902 of Lecture Notes Comput. Sci., pages 84-100. Springer, 2009. Google Scholar
  10. Aurelio Carboni, Steve Lack, and Robert F. C. Walters. Introduction to extensive and distributive categories. J. Pure Appl. Algebra, 84:145-158, 1993. Google Scholar
  11. Calvin C. Elgot. Monadic computation and iterative algebraic theories. In H. E. Rose and J. C. Sheperdson, editors, Logic Colloquium '73, volume 80, pages 175-230, Amsterdam, 1975. North-Holland Publishers. Google Scholar
  12. Joachim Lambek. A fixpoint theorem for complete categories. Math. Z., 103:151-161, 1968. Google Scholar
  13. Stefan Milius. Completely iterative algebras and completely iterative monads. Inform. and Comput., 196:1-41, 2005. Google Scholar
  14. Evelyn Nelson. Iterative algebras. Theoret. Comput. Sci., 25:67-94, 1983. Google Scholar
  15. Jerzy Tiuryn. Unique fixed points vs. least fixed points. Theoret. Comput. Sci., 12:229-254, 1980. Google Scholar
  16. Věra Trnková. Descriptive classification of set functors ii. Comment. Math. Univ. Carolin., 12:345-357, 1971. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact