A combinatorial approach to higher-order structure for polynomial functors
View / Open Files
Journal Title
LIPIcs – Leibniz International Proceedings in Informatics
Conference Name
7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022)
ISSN
1868-8969
ISBN
978-3-95977-233-4
Type
Conference Object
This Version
VoR
Metadata
Show full item recordCitation
Fiore, M., Galal, Z., & Paquet, H. (2022). A combinatorial approach to higher-order structure for polynomial functors. LIPIcs – Leibniz International Proceedings in Informatics https://doi.org/10.4230/LIPIcs.FSCD.2022.31
Abstract
Polynomial functors are categorical structures used in a variety of applications across theoretical computer science; for instance, in database theory, denotational semantics, functional programming, and type theory. A well-known problem is that the bicategory of finitary polynomial functors between categories of indexed sets is not cartesian closed, despite its success and influence on denotational models and linear logic.
This paper introduces a formal bridge between the model of finitary polynomial functors and the combinatorial theory of generalised species of structures. Our approach consists in viewing finitary polynomial functors as free analytic functors, which correspond to free generalised species. In order
to systematically consider finitary polynomial functors from this combinatorial perspective, we study a model of groupoids with additional logical structure; this is used to constrain the generalised species between them. The result is a new cartesian closed bicategory that embeds finitary polynomial functors.
Sponsorship
Research partially supported by EPSRC grant EP/V002309/1.
Funder references
EPSRC (EP/V002309/1)
Identifiers
External DOI: https://doi.org/10.4230/LIPIcs.FSCD.2022.31
This record's URL: https://www.repository.cam.ac.uk/handle/1810/338331
Statistics
Total file downloads (since January 2020). For more information on metrics see the
IRUS guide.
Recommended or similar items
The current recommendation prototype on the Apollo Repository will be turned off on 03 February 2023. Although the pilot has been fruitful for both parties, the service provider IKVA is focusing on horizon scanning products and so the recommender service can no longer be supported. We recognise the importance of recommender services in supporting research discovery and are evaluating offerings from other service providers. If you would like to offer feedback on this decision please contact us on: support@repository.cam.ac.uk