Search

In this paper we develop a method to transfer density results for primitive automatic sequences to logarithmic-density results for general automatic sequences. As an application we show that the logarithmic densities of any automatic sequence along squares (n^2)_{n\geq 0} and primes (p_n)_{n\geq 1} exist and are computable. Furthermore, we give for these subsequences a criterion to decide whether the densities exist, in which case they are also computable. In particular in the prime case these densities are all rational. We also deduce from a recent result of the third author and Lemańczyk that all subshifts generated by automatic sequences are orthogonal to any bounded multiplicative aperiodic function. [ABSTRACT FROM AUTHOR]

We give a detailed asymptotic analysis of the profiles of random symmetric digital search trees, which are in close connection with the performance of the search complexity of random queries in such trees. While the expected profiles have been analyzed for several decades, the analysis of the variance turns out to be very difficult and challenging, and requires the combination of several different analytic techniques, including Mellin and Laplace transforms, analytic de‐Poissonization, and Laplace convolutions. Our results imply concentration of the profiles in the range where the mean tends to infinity. Moreover, we also obtain a two‐point concentration for the distributions of the height and the saturation level. [ABSTRACT FROM AUTHOR]

Divide-and-conquer recurrences are one of the most studied equations in computer science. Yet, discrete versions of these recurrences, namely ... for some known sequence an and given bj, …j, pj and δj, ...j, present some challenges. The discrete nature of this recurrence (represented by the floor and ceiling functions) introduces certain oscillations not captured by the traditional Master Theorem, for example due to Akra and Bazzi [1998] who primary studied the continuous version of the recurrence. We apply powerful techniques such as Dirichlet series, Mellin-Perron formula, and (extended) Tauberian theorems of Wiener-Ikehara to provide a complete and precise solution to this basic computer science recurrence. We illustrate applicability of our results on several examples including a popular and fast arithmetic coding algorithm due to Boncelet for which we estimate its average redundancy and prove the Central Limit Theorem for the phrase length. To the best of our knowledge, discrete divide and conquer recurrences were not studied in this generality and such detail; in particular, this allows us to compare the redundancy of Boncelet's algorithm to the (asymptotically) optimal Tunstall scheme. [ABSTRACT FROM AUTHOR]

Presents an analytic approach used to examine the height of binary search trees. Description of a binary search tree; Determination of the limiting behavior of the distribution of the height of binary search trees; Proofs of different theorems used.