Search Results

Documents authored by Adamek, Jiri

Found 3 Possible Name Variants:

Adamek, Jiri

Document
DOI: 10.4230/LIPIcs.CALCO.2023.10
Strongly Finitary Monads for Varieties of Quantitative Algebras

Authors: Jiří Adámek, Matěj Dostál, and Jiří Velebil

Published in: LIPIcs, Volume 270, 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)

Abstract
Quantitative algebras are algebras enriched in the category Met of metric spaces or UMet of ultrametric spaces so that all operations are nonexpanding. Mardare, Plotkin and Panangaden introduced varieties (aka 1-basic varieties) as classes of quantitative algebras presented by quantitative equations. We prove that, when restricted to ultrametrics, varieties bijectively correspond to strongly finitary monads T on UMet. This means that T is the left Kan extension of its restriction to finite discrete spaces. An analogous result holds in the category CUMet of complete ultrametric spaces.
Cite as

Jiří Adámek, Matěj Dostál, and Jiří Velebil. Strongly Finitary Monads for Varieties of Quantitative Algebras. In 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 270, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2023.10,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i} and Dost\'{a}l, Mat\v{e}j and Velebil, Ji\v{r}{\'\i}},
  title =	{{Strongly Finitary Monads for Varieties of Quantitative Algebras}},
  booktitle =	{10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-287-7},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{270},
  editor =	{Baldan, Paolo and de Paiva, Valeria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2023.10},
  URN =		{urn:nbn:de:0030-drops-188078},
  doi =		{10.4230/LIPIcs.CALCO.2023.10},
  annote =	{Keywords: quantitative algebras, ultra-quantitative algebras, strongly finitary monads, varieties}
}
Document
(Co)algebraic pearls
DOI: 10.4230/LIPIcs.CALCO.2023.21
On Kripke, Vietoris and Hausdorff Polynomial Functors ((Co)algebraic pearls)

Authors: Jiří Adámek, Stefan Milius, and Lawrence S. Moss

Published in: LIPIcs, Volume 270, 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)

Abstract
The Vietoris space of compact subsets of a given Hausdorff space yields an endofunctor V on the category of Hausdorff spaces. Vietoris polynomial endofunctors on that category are built from V, the identity and constant functors by forming products, coproducts and compositions. These functors are known to have terminal coalgebras and we deduce that they also have initial algebras. We present an analogous class of endofunctors on the category of extended metric spaces, using in lieu of V the Hausdorff functor ℋ. We prove that the ensuing Hausdorff polynomial functors have terminal coalgebras and initial algebras. Whereas the canonical constructions of terminal coalgebras for Vietoris polynomial functors takes ω steps, one needs ω + ω steps in general for Hausdorff ones. We also give a new proof that the closed set functor on metric spaces has no fixed points.
Cite as

Jiří Adámek, Stefan Milius, and Lawrence S. Moss. On Kripke, Vietoris and Hausdorff Polynomial Functors ((Co)algebraic pearls). In 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 270, pp. 21:1-21:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2023.21,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i} and Milius, Stefan and Moss, Lawrence S.},
  title =	{{On Kripke, Vietoris and Hausdorff Polynomial Functors}},
  booktitle =	{10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)},
  pages =	{21:1--21:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-287-7},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{270},
  editor =	{Baldan, Paolo and de Paiva, Valeria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2023.21},
  URN =		{urn:nbn:de:0030-drops-188189},
  doi =		{10.4230/LIPIcs.CALCO.2023.21},
  annote =	{Keywords: Hausdorff functor, Vietoris functor, initial algebra, terminal coalgebra}
}
Document
(Co)algebraic pearls
DOI: 10.4230/LIPIcs.CALCO.2021.5
Initial Algebras Without Iteration ((Co)algebraic pearls)

Authors: Jiří Adámek, Stefan Milius, and Lawrence S. Moss

Published in: LIPIcs, Volume 211, 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)

Abstract
The Initial Algebra Theorem by Trnková et al. states, under mild assumptions, that an endofunctor has an initial algebra provided it has a pre-fixed point. The proof crucially depends on transfinitely iterating the functor and in fact shows that, equivalently, the (transfinite) initial-algebra chain stops. We give a constructive proof of the Initial Algebra Theorem that avoids transfinite iteration of the functor. For a given pre-fixed point A of the functor, it uses Pataraia’s theorem to obtain the least fixed point of a monotone function on the partial order formed by all subobjects of A. Thanks to properties of recursive coalgebras, this least fixed point yields an initial algebra. We obtain new results on fixed points and initial algebras in categories enriched over directed-complete partial orders, again without iteration. Using transfinite iteration we equivalently obtain convergence of the initial-algebra chain as an equivalent condition, overall yielding a streamlined version of the original proof.
Cite as

Jiří Adámek, Stefan Milius, and Lawrence S. Moss. Initial Algebras Without Iteration ((Co)algebraic pearls). In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2021.5,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i} and Milius, Stefan and Moss, Lawrence S.},
  title =	{{Initial Algebras Without Iteration}},
  booktitle =	{9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-212-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{211},
  editor =	{Gadducci, Fabio and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2021.5},
  URN =		{urn:nbn:de:0030-drops-153606},
  doi =		{10.4230/LIPIcs.CALCO.2021.5},
  annote =	{Keywords: Initial algebra, Pataraia’s theorem, recursive coalgebra, initial-algebra chain}
}
Document
(Co)algebraic pearls
DOI: 10.4230/LIPIcs.CALCO.2021.6
Which Categories Are Varieties? ((Co)algebraic pearls)

Authors: Jiří Adámek and Jiří Rosický

Published in: LIPIcs, Volume 211, 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)

Abstract
Categories equivalent to single-sorted varieties of finitary algebras were characterized in the famous dissertation of Lawvere. We present a new proof of a slightly sharpened version: those are precisely the categories with kernel pairs and reflexive coequalizers having an abstractly finite, effective strong generator. A completely analogous result is proved for varieties of many-sorted algebras provided that there are only finitely many sorts. In case of infinitely many sorts a slightly weaker result is presented: instead of being abstractly finite, the generator is required to consist of finitely presentable objects.
Cite as

Jiří Adámek and Jiří Rosický. Which Categories Are Varieties? ((Co)algebraic pearls). In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2021.6,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i} and Rosick\'{y}, Ji\v{r}{\'\i}},
  title =	{{Which Categories Are Varieties?}},
  booktitle =	{9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-212-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{211},
  editor =	{Gadducci, Fabio and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2021.6},
  URN =		{urn:nbn:de:0030-drops-153610},
  doi =		{10.4230/LIPIcs.CALCO.2021.6},
  annote =	{Keywords: variety, many-sorted algebra, abstractly finite object, effective object, strong generator}
}
Document
DOI: 10.4230/LIPIcs.CSL.2020.7
On Free Completely Iterative Algebras

Authors: Jiří Adámek

Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{adamek:LIPIcs.CSL.2020.7,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i}},
  title =	{{On Free Completely Iterative Algebras}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Fern\'{a}ndez, Maribel and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.7},
  URN =		{urn:nbn:de:0030-drops-116503},
  doi =		{10.4230/LIPIcs.CSL.2020.7},
  annote =	{Keywords: free algebra, completely iterative algebra, terminal coalgebra, initial algebra, finitary functor}
}
Document
DOI: 10.4230/LIPIcs.CALCO.2019.12
On Terminal Coalgebras Derived from Initial Algebras

Authors: Jiří Adámek

Published in: LIPIcs, Volume 139, 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)

Abstract
A number of important set functors have countable initial algebras, but terminal coalgebras are uncountable or even non-existent. We prove that the countable cardinality is an anomaly: every set functor with an initial algebra of a finite or uncountable regular cardinality has a terminal coalgebra of the same cardinality. We also present a number of categories that are algebraically complete and cocomplete, i.e., every endofunctor has an initial algebra and a terminal coalgebra. Finally, for finitary set functors we prove that the initial algebra mu F and terminal coalgebra nu F carry a canonical ultrametric with the joint Cauchy completion. And the algebra structure of mu F determines, by extending its inverse continuously, the coalgebra structure of nu F.
Cite as

Jiří Adámek. On Terminal Coalgebras Derived from Initial Algebras. In 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 139, pp. 12:1-12:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{adamek:LIPIcs.CALCO.2019.12,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i}},
  title =	{{On Terminal Coalgebras Derived from Initial Algebras}},
  booktitle =	{8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)},
  pages =	{12:1--12:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-120-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{139},
  editor =	{Roggenbach, Markus and Sokolova, Ana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2019.12},
  URN =		{urn:nbn:de:0030-drops-114403},
  doi =		{10.4230/LIPIcs.CALCO.2019.12},
  annote =	{Keywords: terminal coalgebras, initial algebras, algebraically complete category, finitary functor, fixed points of functors}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.43
Eilenberg Theorems for Free

Authors: Henning Urbat, Jiri Adámek, Liang-Ting Chen, and Stefan Milius

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Eilenberg-type correspondences, relating varieties of languages (e.g., of finite words, infinite words, or trees) to pseudovarieties of finite algebras, form the backbone of algebraic language theory. We show that they all arise from the same recipe: one models languages and the algebras recognizing them by monads on an algebraic category, and applies a Stone-type duality. Our main contribution is a variety theorem that covers e.g. Wilke's and Pin's work on infinity-languages, the variety theorem for cost functions of Daviaud, Kuperberg, and Pin, and unifies the two categorical approaches of Bojanczyk and of Adamek et al. In addition we derive new results, such as an extension of the local variety theorem of Gehrke, Grigorieff, and Pin from finite to infinite words.
Cite as

Henning Urbat, Jiri Adámek, Liang-Ting Chen, and Stefan Milius. Eilenberg Theorems for Free. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{urbat_et_al:LIPIcs.MFCS.2017.43,
  author =	{Urbat, Henning and Ad\'{a}mek, Jiri and Chen, Liang-Ting and Milius, Stefan},
  title =	{{Eilenberg Theorems for Free}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{43:1--43:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.43},
  URN =		{urn:nbn:de:0030-drops-81032},
  doi =		{10.4230/LIPIcs.MFCS.2017.43},
  annote =	{Keywords: Eilenberg's theorem, variety of languages, pseudovariety, monad, duality}
}
Document
DOI: 10.4230/LIPIcs.CALCO.2017.3
On Corecursive Algebras for Functors Preserving Coproducts

Authors: Jiri Adámek and Stefan Milius

Published in: LIPIcs, Volume 72, 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2017.3,
  author =	{Ad\'{a}mek, Jiri and Milius, Stefan},
  title =	{{On Corecursive Algebras for Functors Preserving Coproducts}},
  booktitle =	{7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-033-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{72},
  editor =	{Bonchi, Filippo and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2017.3},
  URN =		{urn:nbn:de:0030-drops-80298},
  doi =		{10.4230/LIPIcs.CALCO.2017.3},
  annote =	{Keywords: terminal coalgebra, free algebra, corecursive algebra, hyper-extensive category}
}
Document
DOI: 10.4230/LIPIcs.CALCO.2015.1
Syntactic Monoids in a Category

Authors: Jiri Adamek, Stefan Milius, and Henning Urbat

Published in: LIPIcs, Volume 35, 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)

Abstract
The syntactic monoid of a language is generalized to the level of a symmetric monoidal closed category D. This allows for a uniform treatment of several notions of syntactic algebras known in the literature, including the syntactic monoids of Rabin and Scott (D = sets), the syntactic semirings of Polák (D = semilattices), and the syntactic associative algebras of Reutenauer (D = vector spaces). Assuming that D is a commutative variety of algebras, we prove that the syntactic D-monoid of a language L can be constructed as a quotient of a free D-monoid modulo the syntactic congruence of L, and that it is isomorphic to the transition D-monoid of the minimal automaton for L in D. Furthermore, in the case where the variety D is locally finite, we characterize the regular languages as precisely the languages with finite syntactic D-monoids.
Cite as

Jiri Adamek, Stefan Milius, and Henning Urbat. Syntactic Monoids in a Category. In 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 35, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2015.1,
  author =	{Adamek, Jiri and Milius, Stefan and Urbat, Henning},
  title =	{{Syntactic Monoids in a Category}},
  booktitle =	{6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)},
  pages =	{1--16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-84-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{35},
  editor =	{Moss, Lawrence S. and Sobocinski, Pawel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2015.1},
  URN =		{urn:nbn:de:0030-drops-55235},
  doi =		{10.4230/LIPIcs.CALCO.2015.1},
  annote =	{Keywords: Syntactic monoid, transition monoid, algebraic automata theory, duality, coalgebra, algebra, symmetric monoidal closed category, commutative variety}
}
Document
DOI: 10.4230/LIPIcs.CSL.2011.5
Power-Set Functors and Saturated Trees

Authors: Jiri Adamek, Stefan Milius, Lawrence S. Moss, and Lurdes Sousa

Published in: LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011)

Abstract
We combine ideas coming from several fields, including modal logic, coalgebra, and set theory. Modally saturated trees were introduced by K. Fine in 1975. We give a new purely combinatorial formulation of modally saturated trees, and we prove that they form the limit of the final omega-op-chain of the finite power-set functor Pf. From that, we derive an alternative proof of J. Worrell's description of the final coalgebra as the coalgebra of all strongly extensional, finitely branching trees. In the other direction, we represent the final coalgebra for Pf in terms of certain maximal consistent sets in the modal logic K. We also generalize Worrell's result to M-labeled trees for a commutative monoid M, yielding a final coalgebra for the corresponding functor Mf studied by H. P. Gumm and T. Schröder. We introduce the concept of an i-saturated tree for all ordinals i, and then prove that the i-th step in the final chain of the power set functor consists of all i-saturated trees. This leads to a new description of the final coalgebra for the restricted power-set functors Plambda (of subsets of cardinality smaller than lambda).
Cite as

Jiri Adamek, Stefan Milius, Lawrence S. Moss, and Lurdes Sousa. Power-Set Functors and Saturated Trees. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 5-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CSL.2011.5,
  author =	{Adamek, Jiri and Milius, Stefan and Moss, Lawrence S. and Sousa, Lurdes},
  title =	{{Power-Set Functors and Saturated  Trees}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{5--19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Bezem, Marc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.5},
  URN =		{urn:nbn:de:0030-drops-32194},
  doi =		{10.4230/LIPIcs.CSL.2011.5},
  annote =	{Keywords: saturated tree, extensional tree, final coalgebra, power-set functor, modal logic}
}

Adámek, Jiri

Document
DOI: 10.4230/LIPIcs.CALCO.2023.10
Strongly Finitary Monads for Varieties of Quantitative Algebras

Authors: Jiří Adámek, Matěj Dostál, and Jiří Velebil

Published in: LIPIcs, Volume 270, 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)

Abstract
Quantitative algebras are algebras enriched in the category Met of metric spaces or UMet of ultrametric spaces so that all operations are nonexpanding. Mardare, Plotkin and Panangaden introduced varieties (aka 1-basic varieties) as classes of quantitative algebras presented by quantitative equations. We prove that, when restricted to ultrametrics, varieties bijectively correspond to strongly finitary monads T on UMet. This means that T is the left Kan extension of its restriction to finite discrete spaces. An analogous result holds in the category CUMet of complete ultrametric spaces.
Cite as

Jiří Adámek, Matěj Dostál, and Jiří Velebil. Strongly Finitary Monads for Varieties of Quantitative Algebras. In 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 270, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2023.10,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i} and Dost\'{a}l, Mat\v{e}j and Velebil, Ji\v{r}{\'\i}},
  title =	{{Strongly Finitary Monads for Varieties of Quantitative Algebras}},
  booktitle =	{10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-287-7},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{270},
  editor =	{Baldan, Paolo and de Paiva, Valeria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2023.10},
  URN =		{urn:nbn:de:0030-drops-188078},
  doi =		{10.4230/LIPIcs.CALCO.2023.10},
  annote =	{Keywords: quantitative algebras, ultra-quantitative algebras, strongly finitary monads, varieties}
}
Document
(Co)algebraic pearls
DOI: 10.4230/LIPIcs.CALCO.2023.21
On Kripke, Vietoris and Hausdorff Polynomial Functors ((Co)algebraic pearls)

Authors: Jiří Adámek, Stefan Milius, and Lawrence S. Moss

Published in: LIPIcs, Volume 270, 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)

Abstract
The Vietoris space of compact subsets of a given Hausdorff space yields an endofunctor V on the category of Hausdorff spaces. Vietoris polynomial endofunctors on that category are built from V, the identity and constant functors by forming products, coproducts and compositions. These functors are known to have terminal coalgebras and we deduce that they also have initial algebras. We present an analogous class of endofunctors on the category of extended metric spaces, using in lieu of V the Hausdorff functor ℋ. We prove that the ensuing Hausdorff polynomial functors have terminal coalgebras and initial algebras. Whereas the canonical constructions of terminal coalgebras for Vietoris polynomial functors takes ω steps, one needs ω + ω steps in general for Hausdorff ones. We also give a new proof that the closed set functor on metric spaces has no fixed points.
Cite as

Jiří Adámek, Stefan Milius, and Lawrence S. Moss. On Kripke, Vietoris and Hausdorff Polynomial Functors ((Co)algebraic pearls). In 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 270, pp. 21:1-21:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2023.21,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i} and Milius, Stefan and Moss, Lawrence S.},
  title =	{{On Kripke, Vietoris and Hausdorff Polynomial Functors}},
  booktitle =	{10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)},
  pages =	{21:1--21:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-287-7},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{270},
  editor =	{Baldan, Paolo and de Paiva, Valeria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2023.21},
  URN =		{urn:nbn:de:0030-drops-188189},
  doi =		{10.4230/LIPIcs.CALCO.2023.21},
  annote =	{Keywords: Hausdorff functor, Vietoris functor, initial algebra, terminal coalgebra}
}
Document
(Co)algebraic pearls
DOI: 10.4230/LIPIcs.CALCO.2021.5
Initial Algebras Without Iteration ((Co)algebraic pearls)

Authors: Jiří Adámek, Stefan Milius, and Lawrence S. Moss

Published in: LIPIcs, Volume 211, 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)

Abstract
The Initial Algebra Theorem by Trnková et al. states, under mild assumptions, that an endofunctor has an initial algebra provided it has a pre-fixed point. The proof crucially depends on transfinitely iterating the functor and in fact shows that, equivalently, the (transfinite) initial-algebra chain stops. We give a constructive proof of the Initial Algebra Theorem that avoids transfinite iteration of the functor. For a given pre-fixed point A of the functor, it uses Pataraia’s theorem to obtain the least fixed point of a monotone function on the partial order formed by all subobjects of A. Thanks to properties of recursive coalgebras, this least fixed point yields an initial algebra. We obtain new results on fixed points and initial algebras in categories enriched over directed-complete partial orders, again without iteration. Using transfinite iteration we equivalently obtain convergence of the initial-algebra chain as an equivalent condition, overall yielding a streamlined version of the original proof.
Cite as

Jiří Adámek, Stefan Milius, and Lawrence S. Moss. Initial Algebras Without Iteration ((Co)algebraic pearls). In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2021.5,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i} and Milius, Stefan and Moss, Lawrence S.},
  title =	{{Initial Algebras Without Iteration}},
  booktitle =	{9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-212-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{211},
  editor =	{Gadducci, Fabio and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2021.5},
  URN =		{urn:nbn:de:0030-drops-153606},
  doi =		{10.4230/LIPIcs.CALCO.2021.5},
  annote =	{Keywords: Initial algebra, Pataraia’s theorem, recursive coalgebra, initial-algebra chain}
}
Document
(Co)algebraic pearls
DOI: 10.4230/LIPIcs.CALCO.2021.6
Which Categories Are Varieties? ((Co)algebraic pearls)

Authors: Jiří Adámek and Jiří Rosický

Published in: LIPIcs, Volume 211, 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)

Abstract
Categories equivalent to single-sorted varieties of finitary algebras were characterized in the famous dissertation of Lawvere. We present a new proof of a slightly sharpened version: those are precisely the categories with kernel pairs and reflexive coequalizers having an abstractly finite, effective strong generator. A completely analogous result is proved for varieties of many-sorted algebras provided that there are only finitely many sorts. In case of infinitely many sorts a slightly weaker result is presented: instead of being abstractly finite, the generator is required to consist of finitely presentable objects.
Cite as

Jiří Adámek and Jiří Rosický. Which Categories Are Varieties? ((Co)algebraic pearls). In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2021.6,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i} and Rosick\'{y}, Ji\v{r}{\'\i}},
  title =	{{Which Categories Are Varieties?}},
  booktitle =	{9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-212-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{211},
  editor =	{Gadducci, Fabio and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2021.6},
  URN =		{urn:nbn:de:0030-drops-153610},
  doi =		{10.4230/LIPIcs.CALCO.2021.6},
  annote =	{Keywords: variety, many-sorted algebra, abstractly finite object, effective object, strong generator}
}
Document
DOI: 10.4230/LIPIcs.CSL.2020.7
On Free Completely Iterative Algebras

Authors: Jiří Adámek

Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{adamek:LIPIcs.CSL.2020.7,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i}},
  title =	{{On Free Completely Iterative Algebras}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Fern\'{a}ndez, Maribel and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.7},
  URN =		{urn:nbn:de:0030-drops-116503},
  doi =		{10.4230/LIPIcs.CSL.2020.7},
  annote =	{Keywords: free algebra, completely iterative algebra, terminal coalgebra, initial algebra, finitary functor}
}
Document
DOI: 10.4230/LIPIcs.CALCO.2019.12
On Terminal Coalgebras Derived from Initial Algebras

Authors: Jiří Adámek

Published in: LIPIcs, Volume 139, 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)

Abstract
A number of important set functors have countable initial algebras, but terminal coalgebras are uncountable or even non-existent. We prove that the countable cardinality is an anomaly: every set functor with an initial algebra of a finite or uncountable regular cardinality has a terminal coalgebra of the same cardinality. We also present a number of categories that are algebraically complete and cocomplete, i.e., every endofunctor has an initial algebra and a terminal coalgebra. Finally, for finitary set functors we prove that the initial algebra mu F and terminal coalgebra nu F carry a canonical ultrametric with the joint Cauchy completion. And the algebra structure of mu F determines, by extending its inverse continuously, the coalgebra structure of nu F.
Cite as

Jiří Adámek. On Terminal Coalgebras Derived from Initial Algebras. In 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 139, pp. 12:1-12:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{adamek:LIPIcs.CALCO.2019.12,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i}},
  title =	{{On Terminal Coalgebras Derived from Initial Algebras}},
  booktitle =	{8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)},
  pages =	{12:1--12:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-120-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{139},
  editor =	{Roggenbach, Markus and Sokolova, Ana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2019.12},
  URN =		{urn:nbn:de:0030-drops-114403},
  doi =		{10.4230/LIPIcs.CALCO.2019.12},
  annote =	{Keywords: terminal coalgebras, initial algebras, algebraically complete category, finitary functor, fixed points of functors}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.43
Eilenberg Theorems for Free

Authors: Henning Urbat, Jiri Adámek, Liang-Ting Chen, and Stefan Milius

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Eilenberg-type correspondences, relating varieties of languages (e.g., of finite words, infinite words, or trees) to pseudovarieties of finite algebras, form the backbone of algebraic language theory. We show that they all arise from the same recipe: one models languages and the algebras recognizing them by monads on an algebraic category, and applies a Stone-type duality. Our main contribution is a variety theorem that covers e.g. Wilke's and Pin's work on infinity-languages, the variety theorem for cost functions of Daviaud, Kuperberg, and Pin, and unifies the two categorical approaches of Bojanczyk and of Adamek et al. In addition we derive new results, such as an extension of the local variety theorem of Gehrke, Grigorieff, and Pin from finite to infinite words.
Cite as

Henning Urbat, Jiri Adámek, Liang-Ting Chen, and Stefan Milius. Eilenberg Theorems for Free. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{urbat_et_al:LIPIcs.MFCS.2017.43,
  author =	{Urbat, Henning and Ad\'{a}mek, Jiri and Chen, Liang-Ting and Milius, Stefan},
  title =	{{Eilenberg Theorems for Free}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{43:1--43:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.43},
  URN =		{urn:nbn:de:0030-drops-81032},
  doi =		{10.4230/LIPIcs.MFCS.2017.43},
  annote =	{Keywords: Eilenberg's theorem, variety of languages, pseudovariety, monad, duality}
}
Document
DOI: 10.4230/LIPIcs.CALCO.2017.3
On Corecursive Algebras for Functors Preserving Coproducts

Authors: Jiri Adámek and Stefan Milius

Published in: LIPIcs, Volume 72, 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2017.3,
  author =	{Ad\'{a}mek, Jiri and Milius, Stefan},
  title =	{{On Corecursive Algebras for Functors Preserving Coproducts}},
  booktitle =	{7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-033-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{72},
  editor =	{Bonchi, Filippo and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2017.3},
  URN =		{urn:nbn:de:0030-drops-80298},
  doi =		{10.4230/LIPIcs.CALCO.2017.3},
  annote =	{Keywords: terminal coalgebra, free algebra, corecursive algebra, hyper-extensive category}
}
Document
DOI: 10.4230/LIPIcs.CALCO.2015.1
Syntactic Monoids in a Category

Authors: Jiri Adamek, Stefan Milius, and Henning Urbat

Published in: LIPIcs, Volume 35, 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)

Abstract
The syntactic monoid of a language is generalized to the level of a symmetric monoidal closed category D. This allows for a uniform treatment of several notions of syntactic algebras known in the literature, including the syntactic monoids of Rabin and Scott (D = sets), the syntactic semirings of Polák (D = semilattices), and the syntactic associative algebras of Reutenauer (D = vector spaces). Assuming that D is a commutative variety of algebras, we prove that the syntactic D-monoid of a language L can be constructed as a quotient of a free D-monoid modulo the syntactic congruence of L, and that it is isomorphic to the transition D-monoid of the minimal automaton for L in D. Furthermore, in the case where the variety D is locally finite, we characterize the regular languages as precisely the languages with finite syntactic D-monoids.
Cite as

Jiri Adamek, Stefan Milius, and Henning Urbat. Syntactic Monoids in a Category. In 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 35, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2015.1,
  author =	{Adamek, Jiri and Milius, Stefan and Urbat, Henning},
  title =	{{Syntactic Monoids in a Category}},
  booktitle =	{6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)},
  pages =	{1--16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-84-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{35},
  editor =	{Moss, Lawrence S. and Sobocinski, Pawel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2015.1},
  URN =		{urn:nbn:de:0030-drops-55235},
  doi =		{10.4230/LIPIcs.CALCO.2015.1},
  annote =	{Keywords: Syntactic monoid, transition monoid, algebraic automata theory, duality, coalgebra, algebra, symmetric monoidal closed category, commutative variety}
}
Document
DOI: 10.4230/LIPIcs.CSL.2011.5
Power-Set Functors and Saturated Trees

Authors: Jiri Adamek, Stefan Milius, Lawrence S. Moss, and Lurdes Sousa

Published in: LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011)

Abstract
We combine ideas coming from several fields, including modal logic, coalgebra, and set theory. Modally saturated trees were introduced by K. Fine in 1975. We give a new purely combinatorial formulation of modally saturated trees, and we prove that they form the limit of the final omega-op-chain of the finite power-set functor Pf. From that, we derive an alternative proof of J. Worrell's description of the final coalgebra as the coalgebra of all strongly extensional, finitely branching trees. In the other direction, we represent the final coalgebra for Pf in terms of certain maximal consistent sets in the modal logic K. We also generalize Worrell's result to M-labeled trees for a commutative monoid M, yielding a final coalgebra for the corresponding functor Mf studied by H. P. Gumm and T. Schröder. We introduce the concept of an i-saturated tree for all ordinals i, and then prove that the i-th step in the final chain of the power set functor consists of all i-saturated trees. This leads to a new description of the final coalgebra for the restricted power-set functors Plambda (of subsets of cardinality smaller than lambda).
Cite as

Jiri Adamek, Stefan Milius, Lawrence S. Moss, and Lurdes Sousa. Power-Set Functors and Saturated Trees. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 5-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CSL.2011.5,
  author =	{Adamek, Jiri and Milius, Stefan and Moss, Lawrence S. and Sousa, Lurdes},
  title =	{{Power-Set Functors and Saturated  Trees}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{5--19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Bezem, Marc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.5},
  URN =		{urn:nbn:de:0030-drops-32194},
  doi =		{10.4230/LIPIcs.CSL.2011.5},
  annote =	{Keywords: saturated tree, extensional tree, final coalgebra, power-set functor, modal logic}
}

Adámek, Jiří

Document
DOI: 10.4230/LIPIcs.CALCO.2023.10
Strongly Finitary Monads for Varieties of Quantitative Algebras

Authors: Jiří Adámek, Matěj Dostál, and Jiří Velebil

Published in: LIPIcs, Volume 270, 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)

Abstract
Quantitative algebras are algebras enriched in the category Met of metric spaces or UMet of ultrametric spaces so that all operations are nonexpanding. Mardare, Plotkin and Panangaden introduced varieties (aka 1-basic varieties) as classes of quantitative algebras presented by quantitative equations. We prove that, when restricted to ultrametrics, varieties bijectively correspond to strongly finitary monads T on UMet. This means that T is the left Kan extension of its restriction to finite discrete spaces. An analogous result holds in the category CUMet of complete ultrametric spaces.
Cite as

Jiří Adámek, Matěj Dostál, and Jiří Velebil. Strongly Finitary Monads for Varieties of Quantitative Algebras. In 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 270, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2023.10,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i} and Dost\'{a}l, Mat\v{e}j and Velebil, Ji\v{r}{\'\i}},
  title =	{{Strongly Finitary Monads for Varieties of Quantitative Algebras}},
  booktitle =	{10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-287-7},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{270},
  editor =	{Baldan, Paolo and de Paiva, Valeria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2023.10},
  URN =		{urn:nbn:de:0030-drops-188078},
  doi =		{10.4230/LIPIcs.CALCO.2023.10},
  annote =	{Keywords: quantitative algebras, ultra-quantitative algebras, strongly finitary monads, varieties}
}
Document
(Co)algebraic pearls
DOI: 10.4230/LIPIcs.CALCO.2023.21
On Kripke, Vietoris and Hausdorff Polynomial Functors ((Co)algebraic pearls)

Authors: Jiří Adámek, Stefan Milius, and Lawrence S. Moss

Published in: LIPIcs, Volume 270, 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)

Abstract
The Vietoris space of compact subsets of a given Hausdorff space yields an endofunctor V on the category of Hausdorff spaces. Vietoris polynomial endofunctors on that category are built from V, the identity and constant functors by forming products, coproducts and compositions. These functors are known to have terminal coalgebras and we deduce that they also have initial algebras. We present an analogous class of endofunctors on the category of extended metric spaces, using in lieu of V the Hausdorff functor ℋ. We prove that the ensuing Hausdorff polynomial functors have terminal coalgebras and initial algebras. Whereas the canonical constructions of terminal coalgebras for Vietoris polynomial functors takes ω steps, one needs ω + ω steps in general for Hausdorff ones. We also give a new proof that the closed set functor on metric spaces has no fixed points.
Cite as

Jiří Adámek, Stefan Milius, and Lawrence S. Moss. On Kripke, Vietoris and Hausdorff Polynomial Functors ((Co)algebraic pearls). In 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 270, pp. 21:1-21:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2023.21,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i} and Milius, Stefan and Moss, Lawrence S.},
  title =	{{On Kripke, Vietoris and Hausdorff Polynomial Functors}},
  booktitle =	{10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)},
  pages =	{21:1--21:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-287-7},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{270},
  editor =	{Baldan, Paolo and de Paiva, Valeria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2023.21},
  URN =		{urn:nbn:de:0030-drops-188189},
  doi =		{10.4230/LIPIcs.CALCO.2023.21},
  annote =	{Keywords: Hausdorff functor, Vietoris functor, initial algebra, terminal coalgebra}
}
Document
(Co)algebraic pearls
DOI: 10.4230/LIPIcs.CALCO.2021.5
Initial Algebras Without Iteration ((Co)algebraic pearls)

Authors: Jiří Adámek, Stefan Milius, and Lawrence S. Moss

Published in: LIPIcs, Volume 211, 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)

Abstract
The Initial Algebra Theorem by Trnková et al. states, under mild assumptions, that an endofunctor has an initial algebra provided it has a pre-fixed point. The proof crucially depends on transfinitely iterating the functor and in fact shows that, equivalently, the (transfinite) initial-algebra chain stops. We give a constructive proof of the Initial Algebra Theorem that avoids transfinite iteration of the functor. For a given pre-fixed point A of the functor, it uses Pataraia’s theorem to obtain the least fixed point of a monotone function on the partial order formed by all subobjects of A. Thanks to properties of recursive coalgebras, this least fixed point yields an initial algebra. We obtain new results on fixed points and initial algebras in categories enriched over directed-complete partial orders, again without iteration. Using transfinite iteration we equivalently obtain convergence of the initial-algebra chain as an equivalent condition, overall yielding a streamlined version of the original proof.
Cite as

Jiří Adámek, Stefan Milius, and Lawrence S. Moss. Initial Algebras Without Iteration ((Co)algebraic pearls). In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2021.5,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i} and Milius, Stefan and Moss, Lawrence S.},
  title =	{{Initial Algebras Without Iteration}},
  booktitle =	{9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-212-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{211},
  editor =	{Gadducci, Fabio and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2021.5},
  URN =		{urn:nbn:de:0030-drops-153606},
  doi =		{10.4230/LIPIcs.CALCO.2021.5},
  annote =	{Keywords: Initial algebra, Pataraia’s theorem, recursive coalgebra, initial-algebra chain}
}
Document
(Co)algebraic pearls
DOI: 10.4230/LIPIcs.CALCO.2021.6
Which Categories Are Varieties? ((Co)algebraic pearls)

Authors: Jiří Adámek and Jiří Rosický

Published in: LIPIcs, Volume 211, 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)

Abstract
Categories equivalent to single-sorted varieties of finitary algebras were characterized in the famous dissertation of Lawvere. We present a new proof of a slightly sharpened version: those are precisely the categories with kernel pairs and reflexive coequalizers having an abstractly finite, effective strong generator. A completely analogous result is proved for varieties of many-sorted algebras provided that there are only finitely many sorts. In case of infinitely many sorts a slightly weaker result is presented: instead of being abstractly finite, the generator is required to consist of finitely presentable objects.
Cite as

Jiří Adámek and Jiří Rosický. Which Categories Are Varieties? ((Co)algebraic pearls). In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2021.6,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i} and Rosick\'{y}, Ji\v{r}{\'\i}},
  title =	{{Which Categories Are Varieties?}},
  booktitle =	{9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-212-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{211},
  editor =	{Gadducci, Fabio and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2021.6},
  URN =		{urn:nbn:de:0030-drops-153610},
  doi =		{10.4230/LIPIcs.CALCO.2021.6},
  annote =	{Keywords: variety, many-sorted algebra, abstractly finite object, effective object, strong generator}
}
Document
DOI: 10.4230/LIPIcs.CSL.2020.7
On Free Completely Iterative Algebras

Authors: Jiří Adámek

Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{adamek:LIPIcs.CSL.2020.7,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i}},
  title =	{{On Free Completely Iterative Algebras}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Fern\'{a}ndez, Maribel and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.7},
  URN =		{urn:nbn:de:0030-drops-116503},
  doi =		{10.4230/LIPIcs.CSL.2020.7},
  annote =	{Keywords: free algebra, completely iterative algebra, terminal coalgebra, initial algebra, finitary functor}
}
Document
DOI: 10.4230/LIPIcs.CALCO.2019.12
On Terminal Coalgebras Derived from Initial Algebras

Authors: Jiří Adámek

Published in: LIPIcs, Volume 139, 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)

Abstract
A number of important set functors have countable initial algebras, but terminal coalgebras are uncountable or even non-existent. We prove that the countable cardinality is an anomaly: every set functor with an initial algebra of a finite or uncountable regular cardinality has a terminal coalgebra of the same cardinality. We also present a number of categories that are algebraically complete and cocomplete, i.e., every endofunctor has an initial algebra and a terminal coalgebra. Finally, for finitary set functors we prove that the initial algebra mu F and terminal coalgebra nu F carry a canonical ultrametric with the joint Cauchy completion. And the algebra structure of mu F determines, by extending its inverse continuously, the coalgebra structure of nu F.
Cite as

Jiří Adámek. On Terminal Coalgebras Derived from Initial Algebras. In 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 139, pp. 12:1-12:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{adamek:LIPIcs.CALCO.2019.12,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i}},
  title =	{{On Terminal Coalgebras Derived from Initial Algebras}},
  booktitle =	{8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)},
  pages =	{12:1--12:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-120-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{139},
  editor =	{Roggenbach, Markus and Sokolova, Ana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2019.12},
  URN =		{urn:nbn:de:0030-drops-114403},
  doi =		{10.4230/LIPIcs.CALCO.2019.12},
  annote =	{Keywords: terminal coalgebras, initial algebras, algebraically complete category, finitary functor, fixed points of functors}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.43
Eilenberg Theorems for Free

Authors: Henning Urbat, Jiri Adámek, Liang-Ting Chen, and Stefan Milius

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Eilenberg-type correspondences, relating varieties of languages (e.g., of finite words, infinite words, or trees) to pseudovarieties of finite algebras, form the backbone of algebraic language theory. We show that they all arise from the same recipe: one models languages and the algebras recognizing them by monads on an algebraic category, and applies a Stone-type duality. Our main contribution is a variety theorem that covers e.g. Wilke's and Pin's work on infinity-languages, the variety theorem for cost functions of Daviaud, Kuperberg, and Pin, and unifies the two categorical approaches of Bojanczyk and of Adamek et al. In addition we derive new results, such as an extension of the local variety theorem of Gehrke, Grigorieff, and Pin from finite to infinite words.
Cite as

Henning Urbat, Jiri Adámek, Liang-Ting Chen, and Stefan Milius. Eilenberg Theorems for Free. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{urbat_et_al:LIPIcs.MFCS.2017.43,
  author =	{Urbat, Henning and Ad\'{a}mek, Jiri and Chen, Liang-Ting and Milius, Stefan},
  title =	{{Eilenberg Theorems for Free}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{43:1--43:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.43},
  URN =		{urn:nbn:de:0030-drops-81032},
  doi =		{10.4230/LIPIcs.MFCS.2017.43},
  annote =	{Keywords: Eilenberg's theorem, variety of languages, pseudovariety, monad, duality}
}
Document
DOI: 10.4230/LIPIcs.CALCO.2017.3
On Corecursive Algebras for Functors Preserving Coproducts

Authors: Jiri Adámek and Stefan Milius

Published in: LIPIcs, Volume 72, 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2017.3,
  author =	{Ad\'{a}mek, Jiri and Milius, Stefan},
  title =	{{On Corecursive Algebras for Functors Preserving Coproducts}},
  booktitle =	{7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-033-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{72},
  editor =	{Bonchi, Filippo and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2017.3},
  URN =		{urn:nbn:de:0030-drops-80298},
  doi =		{10.4230/LIPIcs.CALCO.2017.3},
  annote =	{Keywords: terminal coalgebra, free algebra, corecursive algebra, hyper-extensive category}
}
Document
DOI: 10.4230/LIPIcs.CALCO.2015.1
Syntactic Monoids in a Category

Authors: Jiri Adamek, Stefan Milius, and Henning Urbat

Published in: LIPIcs, Volume 35, 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)

Abstract
The syntactic monoid of a language is generalized to the level of a symmetric monoidal closed category D. This allows for a uniform treatment of several notions of syntactic algebras known in the literature, including the syntactic monoids of Rabin and Scott (D = sets), the syntactic semirings of Polák (D = semilattices), and the syntactic associative algebras of Reutenauer (D = vector spaces). Assuming that D is a commutative variety of algebras, we prove that the syntactic D-monoid of a language L can be constructed as a quotient of a free D-monoid modulo the syntactic congruence of L, and that it is isomorphic to the transition D-monoid of the minimal automaton for L in D. Furthermore, in the case where the variety D is locally finite, we characterize the regular languages as precisely the languages with finite syntactic D-monoids.
Cite as

Jiri Adamek, Stefan Milius, and Henning Urbat. Syntactic Monoids in a Category. In 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 35, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2015.1,
  author =	{Adamek, Jiri and Milius, Stefan and Urbat, Henning},
  title =	{{Syntactic Monoids in a Category}},
  booktitle =	{6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)},
  pages =	{1--16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-84-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{35},
  editor =	{Moss, Lawrence S. and Sobocinski, Pawel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2015.1},
  URN =		{urn:nbn:de:0030-drops-55235},
  doi =		{10.4230/LIPIcs.CALCO.2015.1},
  annote =	{Keywords: Syntactic monoid, transition monoid, algebraic automata theory, duality, coalgebra, algebra, symmetric monoidal closed category, commutative variety}
}
Document
DOI: 10.4230/LIPIcs.CSL.2011.5
Power-Set Functors and Saturated Trees

Authors: Jiri Adamek, Stefan Milius, Lawrence S. Moss, and Lurdes Sousa

Published in: LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011)

Abstract
We combine ideas coming from several fields, including modal logic, coalgebra, and set theory. Modally saturated trees were introduced by K. Fine in 1975. We give a new purely combinatorial formulation of modally saturated trees, and we prove that they form the limit of the final omega-op-chain of the finite power-set functor Pf. From that, we derive an alternative proof of J. Worrell's description of the final coalgebra as the coalgebra of all strongly extensional, finitely branching trees. In the other direction, we represent the final coalgebra for Pf in terms of certain maximal consistent sets in the modal logic K. We also generalize Worrell's result to M-labeled trees for a commutative monoid M, yielding a final coalgebra for the corresponding functor Mf studied by H. P. Gumm and T. Schröder. We introduce the concept of an i-saturated tree for all ordinals i, and then prove that the i-th step in the final chain of the power set functor consists of all i-saturated trees. This leads to a new description of the final coalgebra for the restricted power-set functors Plambda (of subsets of cardinality smaller than lambda).
Cite as

Jiri Adamek, Stefan Milius, Lawrence S. Moss, and Lurdes Sousa. Power-Set Functors and Saturated Trees. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 5-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CSL.2011.5,
  author =	{Adamek, Jiri and Milius, Stefan and Moss, Lawrence S. and Sousa, Lurdes},
  title =	{{Power-Set Functors and Saturated  Trees}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{5--19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Bezem, Marc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.5},
  URN =		{urn:nbn:de:0030-drops-32194},
  doi =		{10.4230/LIPIcs.CSL.2011.5},
  annote =	{Keywords: saturated tree, extensional tree, final coalgebra, power-set functor, modal logic}
}
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