Enumerating lambda terms by weighted length of their de Bruijn representation
From MaRDI portal
Publication:1706116
DOI10.1016/j.dam.2017.12.042zbMath1382.05006arXiv1707.02101OpenAlexW2964227342MaRDI QIDQ1706116
Olivier Bodini, Bernhard Gittenberger, Zbigniew Gołȩbiewski
Publication date: 21 March 2018
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1707.02101
Asymptotic enumeration (05A16) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Combinatory logic and lambda calculus (03B40)
Related Items (3)
Distribution of variables in lambda-terms with restrictions on De Bruijn indices and De Bruijn levels ⋮ On the enumeration of closures and environments with an application to random generation ⋮ Statistical properties of lambda terms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Asymptotics and random sampling for BCI and BCK lambda terms
- Enumeration of generalized BCI lambda-terms
- In the full propositional logic, 5/8 of classical tautologies are intuitionistically valid
- Probabilities of Boolean functions given by random implicational formulas
- 2-Xor revisited: satisfiability and probabilities of functions
- Generalised and quotient models for random and/or~trees and application to satisfiability
- Counting proofs in propositional logic
- On the number of unary-binary tree-like structures with restrictions on the unary height
- On counting untyped lambda terms
- A Natural Counting of Lambda Terms
- The fraction of large random trees representing a given Boolean function in implicational logic
- Asymptotic Properties of Combinatory Logic
- Pointed versus singular Boltzmann samplers: a comparative analysis
- Singularity Analysis of Generating Functions
- Tautologies over implication with negative literals
- On the Density of Truth of Locally Finite Logics
- Some typical properties of large AND/OR Boolean formulas
- Coloring rules for finite trees, and probabilities of monadic second order sentences
- Counting finite models
- On the number of lambda terms with prescribed size of their De Bruijn representation
- And/Or Trees Revisited
- Boltzmann Samplers for the Random Generation of Combinatorial Structures
- The number of Boolean functions computed by formulas of a given size
- Asymptotically almost all \lambda-terms are strongly normalizing
- The asymptotics of group Russian roulette
- The relation between tree size complexity and probability for Boolean functions generated by uniform random trees
- How big is BCI fragment of BCK logic
- Counting and generating terms in the binary lambda calculus
- Counting and generating lambda terms
- The Boolean functions computed by random Boolean formulas or how to grow the right function
This page was built for publication: Enumerating lambda terms by weighted length of their de Bruijn representation
