Asymptotics and random sampling for BCI and BCK lambda terms

DOI10.1016/J.TCS.2013.01.008MaRDI QIDQ391429zbMATH OpenOpenAlexFDO

Authors 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 generationBCI logical systemBCK logical systemenumeration of lambda terms

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics) (03B47) Asymptotic enumeration (05A16) Combinatory logic and lambda calculus (03B40)

Recommendations

• Enumeration of generalized BCI lambda-terms
• On the asymptotic number of BCK(2)-terms
• Combinatorics of \(\lambda\)-terms: a natural approach
• Lambda terms of bounded unary height
• Counting and generating terms in the binary lambda calculus

Cites work

• scientific article; zbMATH DE number 3489159 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• An optimal algorithm to generate rooted trivalent diagrams and rooted triangular maps
• Analytic combinatorics
• Analytic variations on the Airy distribution
• Asymptotic Methods in Enumeration
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Classical and Intuitionistic Logic Are Asymptotically Identical
• Enumeration of generalized BCI lambda-terms
• Introduction to algorithms.
• On the analysis of linear probing hashing
• On the diameter of random planar graphs
• Quantitative Comparison of Intuitionistic and Classical Logics - Full Propositional System
• Random graphs.
• Random maps, coalescing saddles, singularity analysis, and Airy phenomena
• Statistical properties of simple types
• The asymptotic number of labeled graphs with given degree sequences
• Une théorie combinatoire des séries formelles

Cited in

(17)

• Enumeration of generalized BCI lambda-terms
• Statistical properties of lambda terms
• Asymptotic distribution of parameters in random maps
• A sequent calculus for a semi-associative law
• The genus distribution of cubic graphs and asymptotic number of rooted cubic maps with high genus
• On the asymptotic number of BCK(2)-terms
• Connected chord diagrams and bridgeless maps
• Exact-Size Sampling of Enriched Trees in Linear Time
• scientific article; zbMATH DE number 7455712 (Why is no real title available?)
• Linear lambda terms as invariants of rooted trivalent maps
• Distribution of variables in lambda-terms with restrictions on De Bruijn indices and De Bruijn levels
• How big is BCI fragment of BCK logic
• Counting and generating terms in the binary lambda calculus
• Bijections between planar maps and planar linear normal \(\lambda\)-terms with connectivity condition
• On the number of variables in special classes of random lambda-terms
• 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

This page was built for publication: Asymptotics and random sampling for BCI and BCK lambda terms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q391429)