Repository logo
 

A combinatorial approach to higher-order structure for polynomial functors

Published version
Peer-reviewed

Type

Conference Object

Change log

Authors

Galal, Zeinab 
Paquet, Hugo 

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.

Description

Keywords

Journal Title

LIPIcs – Leibniz International Proceedings in Informatics

Conference Name

7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022)

Journal ISSN

1868-8969

Volume Title

Publisher

Sponsorship
EPSRC (EP/V002309/1)
Research partially supported by EPSRC grant EP/V002309/1.