License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.132
URN: urn:nbn:de:0030-drops-142016
URL: https://drops.dagstuhl.de/opus/volltexte/2021/14201/
Go to the corresponding LIPIcs Volume Portal


Goy, Alexandre ; Petri┼čan, Daniela ; Aiguier, Marc

Powerset-Like Monads Weakly Distribute over Themselves in Toposes and Compact Hausdorff Spaces

pdf-format:
LIPIcs-ICALP-2021-132.pdf (0.9 MB)


Abstract

The powerset monad on the category of sets does not distribute over itself. Nevertheless a weaker form of distributive law of the powerset monad over itself exists and it essentially stems from the canonical Egli-Milner extension of the powerset to the category of relations. On the other hand, any regular category yields a category of relations, and some regular categories also possess a powerset-like monad, as is the Vietoris monad on compact Hausdorff spaces. We derive the Egli-Milner extension in three different frameworks : sets, toposes, and compact Hausdorff spaces. We prove that it corresponds to a monotone weak distributive law in each case by showing that the multiplication extends to relations but the unit does not. We provide an application to coalgebraic determinization of alternating automata.

BibTeX - Entry

@InProceedings{goy_et_al:LIPIcs.ICALP.2021.132,
  author =	{Goy, Alexandre and Petri\c{s}an, Daniela and Aiguier, Marc},
  title =	{{Powerset-Like Monads Weakly Distribute over Themselves in Toposes and Compact Hausdorff Spaces}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{132:1--132:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14201},
  URN =		{urn:nbn:de:0030-drops-142016},
  doi =		{10.4230/LIPIcs.ICALP.2021.132},
  annote =	{Keywords: Egli-Milner relation, weak extension, weak distributive law, weak lifting, powerset monad, Vietoris monad, topos, alternating automaton, generalized determinization}
}

Keywords: Egli-Milner relation, weak extension, weak distributive law, weak lifting, powerset monad, Vietoris monad, topos, alternating automaton, generalized determinization
Collection: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue Date: 2021
Date of publication: 02.07.2021


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