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

DOI10.1016/J.TCS.2014.06.036MaRDI QIDQ401474zbMATH OpenOpenAlexFDO

Authors 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 radiusDirichlet seriesFourier seriesdilation equationcascade algorithmdivide-and-conquer recurrenceradix-rational sequence

Mathematics Subject Classification ID

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) Combinatorics on words (68R15)

Recommendations

• Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence
• Divide-and-conquer recurrences -- classification of asymptotics
• On the solution of linear recurrence equations
• Joint spectral radius, dilation equations, and asymptotic behavior of radix-rational sequences
• Exact and asymptotic solutions of a divide-and-conquer recurrence dividing at half: theory and applications

Cites work

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

Cited in

(16)

• ZAREMBA, SALEM AND THE FRACTAL NATURE OF GHOST DISTRIBUTIONS
• Exact asymptotics of divide-and-conquer recurrences
• General framework
• A note on the relation between recognisable series and regular sequences, and their minimal linear representations
• Asymptotics of divide-and-conquer recurrences via iterated function systems
• Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence
• Output sum of transducers: limiting distribution and periodic fluctuation
• Asymptotic behaviour of a non-commutative rational series with a nonnegative linear representation
• A More Malicious Maitre d’
• Automatic sequences as good weights for ergodic theorems
• Resurrecting the asymptotics of linear recurrences
• Number theoretic aspects of regular sequences
• Analysis of summatory functions of regular sequences: transducer and Pascal's rhombus
• Asymptotic analysis of regular sequences
• Behavior of digital sequences through exotic numeration systems
• On q-quasiadditive and q-quasimultiplicative functions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q401474)