Asymptotics and random sampling for BCI and BCK lambda terms
This paper presents a bijection between combinatorial maps and a class of enriched trees, corresponding to a class of expression trees in some logical systems (constrained lambda terms). Starting from two alternative definitions of combinatorial maps: the classical definition by gluing half-edges, and a definition by non-ambiguous depth-first traversal, we derive non-trivial asymptotic expansions and efficient random generation of logic formulae (syntactic trees) in the BCI or BCK systems. (C) 2013 Elsevier B.V. All rights reserved.
random generation enumeration of lambda terms bci and bck logical systems