[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

Constructive Final Semantics of Finite Bags

Authors Philipp Joram , Niccolò Veltri



PDF
Thumbnail PDF

File

LIPIcs.ITP.2023.20.pdf
  • Filesize: 0.82 MB
  • 19 pages

Document Identifiers

Author Details

Philipp Joram
  • Department of Software Science, Tallinn University of Technology, Estonia
Niccolò Veltri
  • Department of Software Science, Tallinn University of Technology, Estonia

Cite As Get BibTex

Philipp Joram and Niccolò Veltri. Constructive Final Semantics of Finite Bags. In 14th International Conference on Interactive Theorem Proving (ITP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 268, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITP.2023.20

Abstract

Finitely-branching and unlabelled dynamical systems are typically modelled as coalgebras for the finite powerset functor. If states are reachable in multiple ways, coalgebras for the finite bag functor provide a more faithful representation. The final coalgebra of this functor is employed as a denotational domain for the evaluation of such systems. Elements of the final coalgebra are non-wellfounded trees with finite unordered branching, representing the evolution of systems starting from a given initial state.
This paper is dedicated to the construction of the final coalgebra of the finite bag functor in homotopy type theory (HoTT). We first compare various equivalent definitions of finite bags employing higher inductive types, both as sets and as groupoids (in the sense of HoTT). We then analyze a few well-known, classical set-theoretic constructions of final coalgebras in our constructive setting. We show that, in the case of set-based definitions of finite bags, some constructions are intrinsically classical, in the sense that they are equivalent to some weak form of excluded middle. Nevertheless, a type satisfying the universal property of the final coalgebra can be constructed in HoTT employing the groupoid-based definition of finite bags. We conclude by discussing generalizations of our constructions to the wider class of analytic functors.

Subject Classification

ACM Subject Classification
  • Theory of computation → Type theory
  • Theory of computation → Constructive mathematics
Keywords
  • finite bags
  • final coalgebra
  • homotopy type theory
  • Cubical Agda

Metrics

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

References

  1. Michael Abbott, Thorsten Altenkirch, Neil Ghani, and Conor McBride. Constructing polymorphic programs with quotient types. In Dexter Kozen and Carron Shankland, editors, Proc. of 7th Int. Conf. on Mathematics of Program Construction, MPC'04, volume 3125 of LNCS, pages 2-15. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-27764-4_2.
  2. Jirí Adámek and Václav Koubek. On the greatest fixed point of a set functor. Theoretical Computer Science, 150(1):57-75, 1995. URL: https://doi.org/10.1016/0304-3975(95)00011-K.
  3. Benedikt Ahrens, Paolo Capriotti, and Régis Spadotti. Non-wellfounded trees in Homotopy Type Theory. In Thorsten Altenkirch, editor, Proc. of 13th Int. Conf. on Typed Lambda Calculi and Applications, TLCA'15, volume 38 of LIPIcs, pages 17-30. Schloss Dagstuhl, 2015. URL: https://doi.org/10.4230/LIPICS.TLCA.2015.17.
  4. Michael Barr. Terminal coalgebras in well-founded set theory. Theoretical Computer Science, 114(2):299-315, 1993. URL: https://doi.org/10.1016/0304-3975(93)90076-6.
  5. Gilles Barthe, Venanzio Capretta, and Olivier Pons. Setoids in type theory. Journal of Functional Programming, 13(2):261-293, 2003. URL: https://doi.org/10.1017/S0956796802004501.
  6. Douglas Bridges and Fred Richman. Varieties of Constructive Mathematics. Cambridge University Press, 1987. URL: https://doi.org/10.1017/cbo9780511565663.
  7. Paolo Capriotti, Nicolai Kraus, and Andrea Vezzosi. Functions out of higher truncations. In Stephan Kreutzer, editor, Proc. of 24th EACSL Ann. Conf. on Computer Science Logic, CSL'15, volume 41 of Leibniz International Proceedings in Informatics, pages 359-373. Schloss Dagstuhl, 2015. URL: https://doi.org/10.4230/LIPICS.CSL.2015.359.
  8. Vikraman Choudhury and Marcelo Fiore. Free commutative monoids in homotopy type theory. In Proc. of 38th Conf. on Mathematical Foundations of Programming Semantics (MFPS XXXVIII), volume 1. Centre pour la Communication Scientifique Directe (CCSD), 2023. URL: https://doi.org/10.46298/entics.10492.
  9. Vikraman Choudhury, Jacek Karwowski, and Amr Sabry. Symmetries in reversible programming: from symmetric rig groupoids to reversible programming languages. Proc. of the ACM on Programming Languages, 6(POPL):1-32, 2022. URL: https://doi.org/10.1145/3498667.
  10. Eric Finster, Samuel Mimram, Maxime Lucas, and Thomas Seiller. A cartesian bicategory of polynomial functors in homotopy type theory. In Ana Sokolova, editor, Proc. of 37th Conf. on Mathematical Foundations of Programming Semantics, MFPS'21, volume 351 of EPTCS, pages 67-83, 2021. URL: https://doi.org/10.4204/EPTCS.351.5.
  11. Dan Frumin, Herman Geuvers, Léon Gondelman, and Niels van der Weide. Finite sets in homotopy type theory. In June Andronick and Amy P. Felty, editors, Proc. of 7th ACM SIGPLAN Int. Conf. on Certified Programs and Proofs, CPP'18, pages 201-214. ACM, 2018. URL: https://doi.org/10.1145/3167085.
  12. Ryu Hasegawa. Two applications of analytic functors. Theoretical Computer Science, 272(1-2):113-175, 2002. URL: https://doi.org/10.1016/S0304-3975(00)00349-2.
  13. Ichiro Hasuo, Kenta Cho, Toshiki Kataoka, and Bart Jacobs. Coinductive predicates and final sequences in a fibration. In Dexter Kozen and Michael W. Mislove, editors, Proc. of the 29th Conf. on the Mathematical Foundations of Programming Semantics, MFPS'13, volume 298 of ENTCS, pages 197-214. Elsevier, 2013. URL: https://doi.org/10.1016/j.entcs.2013.09.014.
  14. Bart Jacobs. Introduction to Coalgebra: Towards Mathematics of States and Observation, volume 59 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2016. URL: https://doi.org/10.1017/CBO9781316823187.
  15. André Joyal. Foncteurs analytiques et espèces de structures. In Combinatoire énumérative, pages 126-159. Springer Berlin Heidelberg, 1986. URL: https://doi.org/10.1007/bfb0072514.
  16. Joachim Kock. Data Types with Symmetries and Polynomial Functors over Groupoids. In Ulrich Berger and Michael Mislove, editors, Proc. of 28th Conf. on Mathematical Foundations of Programming Semantics, MFPS'12, volume 286 of ENTCS, pages 351-365. Elsevier, 2012. URL: https://doi.org/10.1016/j.entcs.2013.01.001.
  17. Nicolai Kraus, Martín Escardó, Thierry Coquand, and Thorsten Altenkirch. Notions of Anonymous Existence in Martin-Löf Type Theory. Logical Methods in Computer Science, 13(1), 2017. URL: https://doi.org/10.23638/LMCS-13(1:15)2017.
  18. Magnus Baunsgaard Kristensen, Rasmus Ejlers Møgelberg, and Andrea Vezzosi. Greatest HITs: Higher inductive types in coinductive definitions via induction under clocks. In Christel Baier and Dana Fisman, editors, Proc. of 37th Ann. ACM/IEEE Symp. on Logic in Computer Science, LICS'22, pages 42:1-42:13. ACM, 2022. URL: https://doi.org/10.1145/3531130.3533359.
  19. Paul Blain Levy. Similarity quotients as final coalgebras. In Martin Hofmann, editor, Proc. of 14th Int. Conf on Foundations of Software Science and Computational Structures, FoSSaCS'11, volume 6604 of LNCS, pages 27-41. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-19805-2_3.
  20. Nuo Li. Quotient types in type theory. PhD thesis, University of Nottingham, UK, 2015. URL: http://eprints.nottingham.ac.uk/28941/.
  21. Mark Mandelkern. Constructively complete finite sets. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 34(2):97-103, 1988. URL: https://doi.org/10.1002/malq.19880340202.
  22. Stefano Piceghello. Coherence for Monoidal and Symmetric Monoidal Groupoids in Homotopy Type Theory. PhD thesis, University of Bergen, Norway, 2021. URL: https://hdl.handle.net/11250/2830640.
  23. Jan J. M. M. Rutten. Universal coalgebra: a theory of systems. Theoretical Computer Science, 249(1):3-80, 2000. URL: https://doi.org/10.1016/S0304-3975(00)00056-6.
  24. Kristina Sojakova. Higher Inductive Types as Homotopy-Initial Algebras. PhD thesis, Carnegie Mellon University, USA, 2016. URL: http://reports-archive.adm.cs.cmu.edu/anon/anon/usr0/ftp/home/ftp/2016/CMU-CS-16-125.pdf.
  25. The agda/cubical development team. The agda/cubical library, 2018. URL: https://github.com/agda/cubical/.
  26. The Univalent Foundations Program. Homotopy type theory: Univalent foundations of mathematics. https://homotopytypetheory.org/book, Institute for Advanced Study, 2013.
  27. Daniele Turi and Gordon D. Plotkin. Towards a mathematical operational semantics. In Proc. of 12th Ann. IEEE Symp. on Logic in Computer Science, LICS'97, pages 280-291. IEEE Computer Society, 1997. URL: https://doi.org/10.1109/LICS.1997.614955.
  28. Niccolò Veltri and Niels van der Weide. Constructing higher inductive types as groupoid quotients. Logical Methods in Computer Science, 17(2), 2021. URL: https://doi.org/10.23638/LMCS-17(2:8)2021.
  29. Niccolò Veltri. Type-theoretic constructions of the final coalgebra of the finite powerset functor. In Naoki Kobayashi, editor, Proc. of 6th Int. Conf. on Formal Structures for Computation and Deduction, FSCD'21, volume 195 of LIPIcs, pages 22:1-22:18. Schloss Dagstuhl, 2021. URL: https://doi.org/10.4230/LIPICS.FSCD.2021.22.
  30. Andrea Vezzosi, Anders Mörtberg, and Andreas Abel. Cubical Agda: A dependently typed programming language with univalence and higher inductive types. Proc. of the ACM on Programming Languages, 3(ICFP):1-29, 2019. URL: https://doi.org/10.1145/3341691.
  31. Vladimir Voevodsky. An experimental library of formalized mathematics based on the univalent foundations. Mathematical Structures in Computer Science, 25(5):1278-1294, 2015. URL: https://doi.org/10.1017/s0960129514000577.
  32. James Worrell. On the final sequence of a finitary set functor. Theoretical Computer Science, 338(1-3):184-199, 2005. URL: https://doi.org/10.1016/j.tcs.2004.12.009.
  33. Brent Yorgey. Combinatorial Species and Labelled Structures. PhD thesis, University of Pennsylvania, 2014. URL: http://ozark.hendrix.edu/~yorgey/pub/thesis.pdf.
  34. Brent A. Yorgey. Species and functors and types, oh my! In Jeremy Gibbons, editor, Proc. of 3rd ACM Symp. on Haskell, Haskell'10, pages 147-158. ACM, 2010. URL: https://doi.org/10.1145/1863523.1863542.
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