In this article we study the effect of simple semantic reductions on random BST-like expression-trees. Such random unary-binary expression-trees are often used in benchmarks for model-checking tools. We consider the reduction induced by an absorbing pattern for some given operator ⊛, which we apply bottom-up, producing an equivalent (and smaller) tree-expression. Our main result concerns the expected size of a random tree, of given input size n → ∞, after reduction. We show that there are two different thresholds, leading to a total of five regimes, ranging from no significant reduction at all, to almost complete reduction. These regimes are completely characterized according to the probability of the absorbing operator. Our results prove that random BST-like trees have to be considered with care, and that they offer a richer range of behaviours than uniform random trees.

This article is devoted to the study of two arithmetical sources associated with classical partitions, that are both defined through the mediant of two fractions. The Stern-Brocot source is associated with the sequence of all the mediants, while the Sturm source only keeps mediants whose denominator is "not too large". Even though these sources are both of zero Shannon entropy, with very similar Renyi entropies, their probabilistic features yet appear to be quite different. We then study how they influence the behaviour of tries built on words they emit, and we notably focus on the trie depth. The paper deals with Analytic Combinatorics methods, and Dirichlet generating functions, that are usually used and studied in the case of good sources with positive entropy. To the best of our knowledge, the present study is the first one where these powerful methods are applied to a zero-entropy context. In our context, the generating function associated with each source is explicit and related to classical functions in Number Theory, as the ζ function, the double ζ function or the transfer operator associated with the Gauss map. We obtain precise asymptotic estimates for the mean value of the trie depth that prove moreover to be quite different for each source. Then, these sources provide explicit and natural instances which lead to two unusual and different trie behaviours.

In this article, we question the relevance of uniform random models for algorithms that use expressions as inputs. Using a general framework to describe expressions, we prove that if there is a subexpression that is absorbing for a given operator, then, after repeatedly applying the induced simplification to a uniform random expression of size n, we obtain an equivalent expression of constant expected size. This proves that uniform random expressions lack expressivity, as soon as there is an absorbing pattern. For instance, (a+b)^* is absorbing for the union for regular expressions on {a,b}, hence random regular expressions can be drastically reduced using the induced simplification.