18 citations · 53 across the 13 of their papers we have counts for
3 papers · 1 filter
2-Xor revisited: satisfiability and probabilities of functions
Élie de Panafieu, Danièle Gardy, Bernhard Gittenberger +1
The problem 2-Xor-Sat asks for the probability that a random expression, built as a conjunction of clauses , is satisfiable. We revisit this classical problem by giving…
On the number of unary-binary tree-like structures with restrictions on the unary height
Olivier Bodini, Danièle Gardy, Bernhard Gittenberger +1
We consider various classes of Motzkin trees as well as lambda-terms for which we derive asymptotic enumeration results. These classes are defined through various restrictions conc…
On the number of lambda terms with prescribed size of their De Bruijn representation
Bernhard Gittenberger, Zbigniew Gołębiewski
John Tromp introduced the so-called 'binary lambda calculus' as a way to encode lambda terms in terms of binary words. Later, Grygiel and Lescanne conjectured that the number of bi…