Document Open Access Logo

On Free Completely Iterative Algebras

Author Jiří Adámek

PDF
Thumbnail PDF

File

LIPIcs.CSL.2020.7.pdf
  • Filesize: 488 kB
  • 21 pages

Document Identifiers

Author Details

Jiří Adámek
  • Czech Technical University Prague, Czech Republic

Funding

  • Adámek, Jiří: Supported by the Grant Agency of the Czech Republic under the grant 19-00902S.

Cite AsGet BibTex

Jiří Adámek. On Free Completely Iterative Algebras. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CSL.2020.7

Abstract

For every finitary set functor F we demonstrate that free algebras carry a canonical partial order. In case F is bicontinuous, we prove that the cpo obtained as the conservative completion of the free algebra is the free completely iterative algebra. Moreover, the algebra structure of the latter is the unique continuous extension of the algebra structure of the free algebra. For general finitary functors the free algebra and the free completely iterative algebra are proved to be posets sharing the same conservative completion. And for every recursive equation in the free completely iterative algebra the solution is obtained as the join of an ω-chain of approximate solutions in the free algebra.

Subject Classification

ACM Subject Classification
  • Theory of computation → Categorical semantics
Keywords
  • free algebra
  • completely iterative algebra
  • terminal coalgebra
  • initial algebra
  • finitary functor

Metrics

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

Related Versions

References

  1. P. Aczel and N. Mendler. A final coalgebra theorem. CSLI Lecture Notes, 14, 1988. Center for the Study of Languages and Information, Stanford. Google Scholar
  2. J. Adámek. On terminal coalgebras determined by initial algebras. ArXive 2736791. Google Scholar
  3. J. Adámek. Free algebras and automata realizations in the language of categories. Comment. Math. Univ. Carolinae, 15:589-602, 1974. Google Scholar
  4. J. Adámek. Final colagebras are ideal completions if initial algebras. J. Logic Comput., 2:217-242, 2002. Google Scholar
  5. J. Adámek and S. Milius. Terminal coalgebras and free iterative theories. Information and Computation, 204:1139-1172, 2006. Google Scholar
  6. J. Adámek and V. Trnková. Automata and algebras in a category. Academic Publishers, 1990. Google Scholar
  7. B. Banaschewski and E. Nelson. Completions of partially ordered sets. SIAM J. Comput., 11:521-528, 1982. Google Scholar
  8. M. Barr. Terminal coalgebras in well-founded set theory. Theoret. Comput. Sci., 124:182-192, 1994. Google Scholar
  9. C.C. Elgot. Monadic computation and iterative algebraic theories. In Logic Colloqium '73. North Holland Publ. Amsterdam, 1975. Google Scholar
  10. S. Milius. Completely iterative algebras and completely iterative monads. Information and Computation, 196:1-41, 2005. Google Scholar
  11. J. Worrell. On the final sequence of a finitary set functor. Theoret. Comput. Sci., 338:184-199, 2005. 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 Imprint Privacy Contact