Computing absolutely normal numbers in nearly linear time

DOI10.1016/j.ic.2021.104746OpenAlexW3154496493MaRDI QIDQ2051782

Jack H. Lutz, Elvira Mayordomo

Publication date: 25 November 2021

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1611.05911

zbMATH Keywords

algorithmscomputational complexitymartingalesnormal numbersLempel-Ziv parsing

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Normal Numbers and Computer Science ⋮ Algorithmic Fractal Dimensions in Geometric Measure Theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial-time algorithm for computing absolutely normal numbers
• On normal numbers
• Entropy rates and finite-state dimension
• Turing's unpublished algorithm for normal numbers
• Is \(\pi\) normal ?
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Finite-state dimension
• Feasible analysis, randomness, and base invariance
• Why computational complexity requires stricter martingales
• Endliche Automaten und Zufallsfolgen
• On a problem of Steinhaus about normal numbers
• Compression of individual sequences via variable-rate coding
• Computable absolutely Pisot normal numbers
• On the construction of absolutely normal numbers
• Construction of a random sequence
• On Computable Numbers, with an Application to the Entscheidungsproblem

This page was built for publication: Computing absolutely normal numbers in nearly linear time