BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

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


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.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International