1. Asymptotic Distribution of Parameters in Trivalent Maps and Linear Lambda Terms
- Author
-
Bodini, OLivier, Singh, Alexandros, Zeilberger, Noam, Laboratoire d'Informatique de Paris-Nord (LIPN), Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Nord, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Automatisation et ReprésenTation: fOndation du calcUl et de la déducTion (PARTOUT), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Zeilberger, Noam
- Subjects
FOS: Computer and information sciences ,Computer Science - Logic in Computer Science ,[INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL] ,05A16, 05A19, 03B40, 05C30 (Primary) ,FOS: Mathematics ,Mathematics - Combinatorics ,F.4.1 ,G.2.1 ,Combinatorics (math.CO) ,[INFO.INFO-PL] Computer Science [cs]/Programming Languages [cs.PL] ,Logic in Computer Science (cs.LO) - Abstract
Structural properties of large random maps and lambda-terms may be gleaned by studying the limit distributions of various parameters of interest. In our work we focus on restricted classes of maps and their counterparts in the lambda-calculus, building on recent bijective connections between these two domains. In such cases, parameters in maps naturally correspond to parameters in lambda-terms and vice versa. By an interplay between lambda-terms and maps, we obtain various combinatorial specifications which allow us to access the distributions of pairs of related parameters such as: the number of bridges in rooted trivalent maps and of subterms in closed linear lambda-terms, the number of vertices of degree 1 in (1,3)-valent maps and of free variables in open linear lambda-terms etc. To analyse asymptotically these distributions, we introduce appropriate tools: a moment-pumping schema for differential equations and a composition schema inspired by Bender's theorem., Comment: 40 pages, 16 figures
- Published
- 2021
- Full Text
- View/download PDF