Normal numbers and finite automata

We give an elementary and direct proof of the following theorem: A real number is normal to a given integer base if, and only if, its expansion in that base is incompressible by lossless finite-state compressors (these are finite automata augmented with an output transition function such that the au...

Descripción completa

Detalles Bibliográficos
Autores principales: Becher, Verónica Andrea, Heiber, Pablo Ariel
Publicado: 2013
Materias:
Finite state transducers
Finite-state
Input-output
Lossless
Normal numbers
Output transition
Real number
Number theory
Theorem proving
Finite automata
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v477_n_p109_Becher
http://hdl.handle.net/20.500.12110/paper_03043975_v477_n_p109_Becher
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_03043975_v477_n_p109_Becher
record_format dspace
spelling paper:paper_03043975_v477_n_p109_Becher2023-06-08T15:29:39Z Normal numbers and finite automata Becher, Verónica Andrea Heiber, Pablo Ariel Finite state transducers Finite-state Input-output Lossless Normal numbers Output transition Real number Number theory Theorem proving Finite automata We give an elementary and direct proof of the following theorem: A real number is normal to a given integer base if, and only if, its expansion in that base is incompressible by lossless finite-state compressors (these are finite automata augmented with an output transition function such that the automata input-output behaviour is injective; they are also known as injective finite-state transducers). As a corollary we obtain V.N. Agafonov's theorem on the preservation of normality on subsequences selected by finite automata.© 2012 Elsevier B.V. All rights reserved. Fil:Becher, V. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Heiber, P.A. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2013 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v477_n_p109_Becher http://hdl.handle.net/20.500.12110/paper_03043975_v477_n_p109_Becher
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Finite state transducers
Finite-state
Input-output
Lossless
Normal numbers
Output transition
Real number
Number theory
Theorem proving
Finite automata
spellingShingle Finite state transducers
Finite-state
Input-output
Lossless
Normal numbers
Output transition
Real number
Number theory
Theorem proving
Finite automata
Becher, Verónica Andrea
Heiber, Pablo Ariel
Normal numbers and finite automata
topic_facet Finite state transducers
Finite-state
Input-output
Lossless
Normal numbers
Output transition
Real number
Number theory
Theorem proving
Finite automata
description We give an elementary and direct proof of the following theorem: A real number is normal to a given integer base if, and only if, its expansion in that base is incompressible by lossless finite-state compressors (these are finite automata augmented with an output transition function such that the automata input-output behaviour is injective; they are also known as injective finite-state transducers). As a corollary we obtain V.N. Agafonov's theorem on the preservation of normality on subsequences selected by finite automata.© 2012 Elsevier B.V. All rights reserved.
author Becher, Verónica Andrea
Heiber, Pablo Ariel
author_facet Becher, Verónica Andrea
Heiber, Pablo Ariel
author_sort Becher, Verónica Andrea
title Normal numbers and finite automata
title_short Normal numbers and finite automata
title_full Normal numbers and finite automata
title_fullStr Normal numbers and finite automata
title_full_unstemmed Normal numbers and finite automata
title_sort normal numbers and finite automata
publishDate 2013
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v477_n_p109_Becher
http://hdl.handle.net/20.500.12110/paper_03043975_v477_n_p109_Becher
work_keys_str_mv AT becherveronicaandrea normalnumbersandfiniteautomata
AT heiberpabloariel normalnumbersandfiniteautomata
_version_ 1768544502775021568

Ejemplares similares