Normal numbers and finite automata

DOI10.1016/J.TCS.2013.01.019MaRDI QIDQ1945947zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Verónica Becher, Pablo Ariel Heiber

Publication date 17 April 2013

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

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

zbMATH Keywords

Agafonov's theoremexpansionfinite automataincompressibleinjective finite-state transducerslossless finite-state compressorsnormal real numberreal number

Mathematics Subject Classification ID

Special sequences and polynomials (11B83) Formal languages and automata (68Q45)

Recommendations

• Automatic Kolmogorov complexity and normality revisited
• Normal numbers and computer science
• Normality and automata
• On normality in shifts of finite type
• Normality and two-way automata

Cited in

(26)

• Automates finis et ensembles normaux. (Finite automata and normal sets)
• An unpredictability approach to finite-state randomness
• Automatic Kolmogorov complexity and normality revisited
• Finite-state independence
• Generic sequences, transducers and multiplication of normal numbers
• Preservation of normality by non-oblivious group selection
• Preservation of normality by transducers
• Preservation of normality by unambiguous transducers
• Selection rules preserving normality
• Normality and two-way automata
• Normality in non-integer bases and polynomial time randomness
• Normal numbers and limit computable Cantor series
• Finite-state independence and normal sequences
• Automatic Kolmogorov complexity, normality, and finite-state dimension revisited
• Continued fraction normality is not preserved along arithmetic progressions
• scientific article; zbMATH DE number 177152 (Why is no real title available?)
• Normal numbers and computer science
• Normality and automata
• NORMALIZED EXPRESSIONS AND FINITE AUTOMATA
• The Game of Normal Numbers
• Pushdown and Lempel-Ziv depth
• Pebble-depth
• Deterministic pushdown automata can compress some normal sequences
• Agafonov's theorem for finite and infinite alphabets and probability distributions different from equidistribution
• On normality in shifts of finite type
• A normal sequence compressed by PPM* but not by Lempel-Ziv 78

This page was built for publication: Normal numbers and finite automata

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