Asymptotics and random sampling for BCI and BCK lambda terms

DOI10.1016/j.tcs.2013.01.008zbMath1297.68184MaRDI QIDQ391429

Olivier Bodini, Alice Jacquot, Daniéle Gardy

Publication date: 10 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.01.008

zbMATH Keywords

random generation; BCI logical system; BCK logical system; enumeration of lambda terms

Mathematics Subject Classification ID

68R05: Combinatorics in computer science

05A16: Asymptotic enumeration

03B47: Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics)

03B40: Combinatory logic and lambda calculus

Related Items

Unnamed Item, Unnamed Item, Unnamed Item, Asymptotic Distribution of Parameters in Random Maps, Distribution of variables in lambda-terms with restrictions on De Bruijn indices and De Bruijn levels, Counting and generating terms in the binary lambda calculus, Linear lambda terms as invariants of rooted trivalent maps, Bijections between planar maps and planar linear normal \(\lambda\)-terms with connectivity condition, Exact-Size Sampling of Enriched Trees in Linear Time, Enumerating lambda terms by weighted length of their de Bruijn representation, On the number of unary-binary tree-like structures with restrictions on the unary height, Connected chord diagrams and bridgeless maps, Statistical properties of lambda terms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enumeration of generalized BCI lambda-terms
• An optimal algorithm to generate rooted trivalent diagrams and rooted triangular maps
• Une théorie combinatoire des séries formelles
• The asymptotic number of labeled graphs with given degree sequences
• On the analysis of linear probing hashing
• Random maps, coalescing saddles, singularity analysis, and Airy phenomena
• On the diameter of random planar graphs
• Quantitative Comparison of Intuitionistic and Classical Logics - Full Propositional System
• Classical and Intuitionistic Logic Are Asymptotically Identical
• Asymptotic Methods in Enumeration
• Statistical properties of simple types
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Analytic variations on the Airy distribution