Open Collections

A groupoid of permutation trees (with applications to the Taylor expansion of λ-terms)

Banff International Research Station for Mathematical Innovation and Discovery

We introduce a groupoid of trees whose objects are (labelled, planar, rooted) trees, and whose morphisms are trees with permutations attached to internal nodes: we obtain a morphism from T to T' exactly when T' is obtained by permuting the subtrees of each node in T inductively, according to permutations given by the morphism. The degree of a tree is then defined as the cardinality of its group of automorphisms. We are interested in the effect of tree substitution on the degree of trees: tree substitution is a variant of the usual operadic composition of trees, parameterized by a selection of the leaves to be substituted. This study is motivated by an approach to the Taylor expansion of λ-terms recently developed by Federico Olimpieri and myself. In particular, up to a mild generalisation of the above setting, the coefficient of a resource term occurring in the Taylor expansion of a pure λ-term is exactly the inverse of the degree of its syntactic tree.

Mathematics; Category Theory; Homological Algebra; Algebraic Topology; Algebraic Structures

video/mp4

Author affiliation: Aix-Marseille University, France

2023-10-29

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/86387

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/