Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: algebraic and analytic approaches collated

DOI10.1016/j.tcs.2014.06.036zbMath1360.11083OpenAlexW1975849168MaRDI QIDQ401474

Philippe Dumas

Publication date: 27 August 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.06.036

zbMATH Keywords

spectral radiusFourier seriesDirichlet seriesdilation equationcascade algorithmdivide-and-conquer recurrenceradix-rational sequence

Mathematics Subject Classification ID

Combinatorics on words (68R15) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc. (11K16)

Related Items (11)

Automatic sequences as good weights for ergodic theorems ⋮ Analysis of Summatory Functions of Regular Sequences: Transducer and Pascal's Rhombus ⋮ A More Malicious Maitre d’ ⋮ ZAREMBA, SALEM AND THE FRACTAL NATURE OF GHOST DISTRIBUTIONS ⋮ A note on the relation between recognisable series and regular sequences, and their minimal linear representations ⋮ General Framework ⋮ Number Theoretic Aspects of Regular Sequences ⋮ Behavior of digital sequences through exotic numeration systems ⋮ On \(q\)-quasiadditive and \(q\)-quasimultiplicative functions ⋮ Asymptotic analysis of regular sequences ⋮ Output sum of transducers: limiting distribution and periodic fluctuation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new dichotomic algorithm for the uniform random generation of words in regular languages
• The Takagi function: a survey
• Distribution of the sum-of-digits function of random integers: a survey
• On the set of points where Lebesgue's singular function has the derivative zero
• A summation formula related to the binary digits
• A summation formula involving Fibonacci digits
• Hölder exponents and box dimension for self-affine fractal functions
• Uniform refinement of curves
• Systèmes de numération et fonctions fractales relatifs aux substitutions. (Numeration systems and fractal functions related to substitutions)
• On sums of Rudin-Shapiro coefficients. II
• The moments of the Cantor distribution
• The ring of \(k\)-regular sequences
• The fractal structure of rarefied sums of the Thue-Morse sequence
• Sur la fonction sommatoire de la fonction 'somme des chiffres'
• Über Summen von Rudin-Shapiroschen Koeffizienten
• The distribution of the sum-of-digits function
• Asymptotics of divide-and-conquer recurrences: Batcher's sorting algorithm and a minimum Euclidean matching heuristic
• Matrices and quadrature rules for wavelets
• Mellin transforms and asymptotics: Digital sums
• Mellin transforms and asymptotics. The mergesort recurrence
• The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate
• Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence
• Joint spectral radius, dilation equations, and asymptotic behavior of radix-rational sequences
• Dynamical directions in numeration
• The birth of the joint spectral radius: an interview with Gilbert Strang
• On the finiteness property for rational matrices
• Digital Sums and Functional Equations
• Calculation of Moments for a Cantor-Vitali Function
• Some Theorems on Fourier Coefficients
• Subdivision schemes in geometric modelling
• A Correlated Digital Sum Problem Associated with Sums of Three Squares
• A Note on Gray Code and Odd-Even Merge
• Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching
• Two-Scale Difference Equations. I. Existence and Global Regularity of Solutions
• Ten Lectures on Wavelets
• Simple Regularity Criteria for Subdivision Schemes
• Two-Scale Difference Equations II. Local Regularity, Infinite Products of Matrices and Fractals
• The Number of 1’s in Binary Integers: Bounds and Extremal Properties
• Power and Exponential Sums of Digital Sums Related to Binomial Coefficient Parity
• Number of representations related to a linear recurrent basis
• Automatic Sequences
• An analytical construction of the SRB measures for Baker-type maps
• The Takagi Function and Its Properties
• Speeding up the computations on an elliptic curve using addition-subtraction chains
• Analysis of digital functions and applications
• A Sequence of (± 1)-Determinants with Large Values
• An Explicit Expression for Binary Digital Sums
• Note on the Shapiro Polynomials
• On the Number of Binary Digits in a Multiple of Three
• Extreme values of some continuous nowhere differentiable functions
• A simple system of discrete two-scale difference equations

This page was built for publication: Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: algebraic and analytic approaches collated