Document Open Access Logo

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

Authors Alexandre Goy , Daniela Petrişan , Marc Aiguier

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2021.132.pdf
  • Filesize: 0.94 MB
  • 14 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
Keywords
  • Egli-Milner relation
  • weak extension
  • weak distributive law
  • weak lifting
  • powerset monad
  • Vietoris monad
  • topos
  • alternating automaton
  • generalized determinization

Metrics

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

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.

Cite As Get BibTex

Alexandre Goy, Daniela Petrişan, and Marc Aiguier. Powerset-Like Monads Weakly Distribute over Themselves in Toposes and Compact Hausdorff Spaces. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 132:1-132:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.132

Author Details

Alexandre Goy
  • Université Paris-Saclay, CentraleSupélec, MICS, France
Daniela Petrişan
  • Université de Paris, IRIF, France
Marc Aiguier
  • Université Paris-Saclay, CentraleSupélec, MICS, France

References

  1. Jon Beck. Distributive laws. In B. Eckmann, editor, Seminar on Triples and Categorical Homology Theory, pages 119-140, Berlin, Heidelberg, 1969. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/BFb0083084.
  2. Meven Bertrand and Jurriaan Rot. Coalgebraic determinization of alternating automata. arXiv preprint, 2018. URL: http://arxiv.org/abs/1804.02546.
  3. Guram Bezhanishvili, Nick Bezhanishvili, and John Harding. Modal compact Hausdorff spaces. Journal of Logic and Computation, 25(1):1-35, 2015. URL: https://doi.org/10.1093/logcom/exs030.
  4. Guram Bezhanishvili, David Gabelaia, John Harding, and Mamuka Jibladze. Compact Hausdorff spaces with relations and Gleason spaces. Applied Categorical Structures, 27(6):663-686, 2019. URL: https://doi.org/10.1007/s10485-019-09573-x.
  5. Nick Bezhanishvili, Sebastian Enqvist, and Jim de Groot. Duality for instantial neighbourhood logic via coalgebra. In Daniela Petrişan and Jurriaan Rot, editors, Coalgebraic Methods in Computer Science, pages 32-54, Cham, 2020. Springer International Publishing. URL: https://doi.org/10.1007/978-3-030-57201-3_3.
  6. Nick Bezhanishvili, Gaëlle Fontaine, and Yde Venema. Vietoris bisimulations. Journal of Logic and Computation, 20(5):1017-1040, 2010. URL: https://doi.org/10.1093/logcom/exn091.
  7. Aurelio Carboni, G Max Kelly, and Richard J Wood. A 2-categorical approach to change of base and geometric morphisms I. Cahiers de topologie et géométrie différentielle catégoriques, 32(1):47-95, 1991. Google Scholar
  8. Ashok K. Chandra, Dexter C. Kozen, and Larry J. Stockmeyer. Alternation. J. ACM, 28(1):114–133, 1981. URL: https://doi.org/10.1145/322234.322243.
  9. Peter J Freyd and Andre Scedrov. Categories, allegories. Elsevier, 1990. Google Scholar
  10. Richard Garner. The Vietoris monad and weak distributive laws. Applied Categorical Structures, October 2019. URL: https://doi.org/10.1007/s10485-019-09582-w.
  11. Alexandre Goy and Daniela Petrişan. Combining probabilistic and non-deterministic choice via weak distributive laws. In LICS '20: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 454-464, Saarbrücken, Germany, 2020. URL: https://doi.org/10.1145/3373718.3394795.
  12. Peter T Johnstone. Sketches of an Elephant: A Topos Theory Compendium: Volume 1, volume 1. Oxford University Press, 2002. Google Scholar
  13. Bartek Klin and Jurriaan Rot. Coalgebraic trace semantics via forgetful logics. In International Conference on Foundations of Software Science and Computation Structures, pages 151-166. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-46678-0_10.
  14. Bartek Klin and Julian Salamanca. Iterated covariant powerset is not a monad. Electronic Notes in Theoretical Computer Science, 341:261-276, 2018. Proceedings of the Thirty-Fourth Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXIV). URL: https://doi.org/10.1016/j.entcs.2018.11.013.
  15. Clemens Kupke, Alexander Kurz, and Yde Venema. Stone coalgebras. Theoretical Computer Science, 327(1-2):109-134, 2004. URL: https://doi.org/10.1016/j.tcs.2004.07.023.
  16. Saunders MacLane and Ieke Moerdijk. Sheaves in geometry and logic: A first introduction to topos theory. Springer Science & Business Media, 2012. Google Scholar
  17. Vincenzo Marra and Luca Reggio. A characterisation of the category of compact Hausdorff spaces. Theory and Applications of Categories, 35(51):1871-1906, 2020. URL: http://www.tac.mta.ca/tac/volumes/35/51/35-51.pdf.
  18. Colin McLarty. Elementary categories, elementary toposes. Clarendon Press, 1992. Google Scholar
  19. Oege de Moor. Categories, relations and dynamic programming. PhD thesis, University of Oxford, 1992. Google Scholar
  20. Gerhard Osius. Logical and set theoretical tools in elementary topoi. In F. William Lawvere, Christian Maurer, and Gavin C. Wraith, editors, Model Theory and Topoi, pages 297-346, Berlin, Heidelberg, 1975. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/BFb0061299.
  21. Christoph Schubert. Lax Algebras: A Scenic Approach. PhD thesis, Universität Bremen, 2006. Google Scholar
  22. Sam Staton. Relating coalgebraic notions of bisimulation. In International Conference on Algebra and Coalgebra in Computer Science, pages 191-205. Springer, 2009. URL: https://doi.org/10.2168/LMCS-7(1:13)2011.
  23. Daniele Turi. Functorial operational semantics and its denotational dual. PhD thesis, Vrije Universiteit, Amsterdam, 1996. URL: https://www.cs.vu.nl/en/Images/D_Turi_06-06-1996_tcm210-258569.pdf.
  24. Daniele Varacca. Probability, nondeterminism and concurrency: Two denotational models for probabilistic computation. Technical report, PhD thesis, Univ. Aarhus, 2003. BRICS Dissertation Series, 2003. URL: https://www.brics.dk/DS/03/14/BRICS-DS-03-14.pdf.
  25. Stephen Willard. General Topology. Dover Publications, 2004. Google Scholar
  26. M. Zwart and D. Marsden. No-go theorems for distributive laws. In 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-13, Los Alamitos, CA, USA, June 2019. IEEE Computer Society. URL: https://doi.org/10.1109/LICS.2019.8785707.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact