Résumé : Structural properties of large random λ-terms may be gleaned by studying the asymptotic distributions of various parameters of interest, such as the number of free variables, abstractions and applications, and so on. Such properties have been studied for general λ-terms under various considerations such as different notions of size and various structural restrictions. Linear λ-terms, that is, terms where each variable occurs exactly once, form an interesting subsystem of λ-calculus with various combinatorial connections to much-studied classes of objects such as trivalent maps. The purpose of this work is to help shed some light on what the “typical” terms of certain fragments of the linear λ calculus look like. The fragments we deal with in this work may be roughly partitioned into two major categories, the algebraic and the differentially-algebraic one, according to the nature of the specifications they admit.
Dernière modification : Monday 21 September 2020 | Contact : Cyril.Banderier at lipn.univ-paris13.fr |