Normal numbers and finite automata

Mostrar todas las versiones(3)

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

Guardado en:
Detalles Bibliográficos
Autores principales: Becher, V., Heiber, P.A.
Formato: Artículo publishedVersion
Lenguaje:Inglés
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: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 paperaa:paper_03043975_v477_n_p109_Becher
record_format dspace
spelling paperaa:paper_03043975_v477_n_p109_Becher2023-06-12T16:47:30Z Normal numbers and finite automata Theor Comput Sci 2013;477:109-116 Becher, V. Heiber, P.A. 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 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion application/pdf eng info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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)
language Inglés
orig_language_str_mv eng
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, V.
Heiber, P.A.
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.
format Artículo
Artículo
publishedVersion
author Becher, V.
Heiber, P.A.
author_facet Becher, V.
Heiber, P.A.
author_sort Becher, V.
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 http://hdl.handle.net/20.500.12110/paper_03043975_v477_n_p109_Becher
work_keys_str_mv AT becherv normalnumbersandfiniteautomata
AT heiberpa normalnumbersandfiniteautomata
_version_ 1769810336207077376

Ejemplares similares