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

DOI10.1016/J.TCS.2014.06.036zbMATH Open1360.11083OpenAlexW1975849168MaRDI QIDQ401474FDOQ401474

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

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

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)

Cites Work

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

Cited In (14)

• ZAREMBA, SALEM AND THE FRACTAL NATURE OF GHOST DISTRIBUTIONS
• Number Theoretic Aspects of Regular Sequences
• Exact asymptotics of divide-and-conquer recurrences
• Analysis of Summatory Functions of Regular Sequences: Transducer and Pascal's Rhombus
• A note on the relation between recognisable series and regular sequences, and their minimal linear representations
• Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence
• Output sum of transducers: limiting distribution and periodic fluctuation
• A More Malicious Maitre d’
• Automatic sequences as good weights for ergodic theorems
• Resurrecting the asymptotics of linear recurrences
• General Framework
• 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)