License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2011.5
URN: urn:nbn:de:0030-drops-32194
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3219/
Go to the corresponding LIPIcs Volume Portal

Adamek, Jiri ; Milius, Stefan ; Moss, Lawrence S. ; Sousa, Lurdes

Power-Set Functors and Saturated Trees

pdf-format:
6.pdf (0.4 MB)

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).

BibTeX - Entry

@InProceedings{adamek_et_al:LIPIcs:2011:3219,
  author =	{Jiri Adamek and Stefan Milius and Lawrence S. Moss and Lurdes Sousa},
  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 =	{Marc Bezem},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3219},
  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}
}

Keywords: saturated tree, extensional tree, final coalgebra, power-set functor, modal logic
Collection: Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL
Issue Date: 2011
Date of publication: 31.08.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI