Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

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.

Registro:

Documento: Artículo
Título:Normal numbers and finite automata
Autor:Becher, V.; Heiber, P.A.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires and CONICET, Argentina
Palabras clave:Finite state transducers; Finite-state; Input-output; Lossless; Normal numbers; Output transition; Real number; Number theory; Theorem proving; Finite automata
Año:2013
Volumen:477
Página de inicio:109
Página de fin:116
DOI: http://dx.doi.org/10.1016/j.tcs.2013.01.019
Título revista:Theoretical Computer Science
Título revista abreviado:Theor Comput Sci
ISSN:03043975
CODEN:TCSCD
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_03043975_v477_n_p109_Becher.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v477_n_p109_Becher

Referencias:

  • Agafonov, V.N., Normal sequences and finite automata (1968) Soviet Mathematics Doklady, 9, pp. 324-325
  • Borel, É., Les probabilités dénombrables et leurs applications arithmétiques (1909) Rendiconti Del Circolo Matematico di Palermo, 27, pp. 247-271
  • Bourke, C., Hitchcock, J., Vinodch, N., Entropy rates and finite-state dimension (2005) Theoretical Computer Science, 349, pp. 392-406
  • Broglio, A., Liardet, P., Predictions with automata. symbolic dynamics and its applications (1992) Contemporary Mathematics, 135, pp. 111-124. , Also in Proceedings AMS Conference in honor of R. L. Adler. New Haven CT - USA 1991
  • Bugeaud, Y., (2012) Distribution Modulo One and Diophantine Approximation, , Series: Cambridge Tracts in Mathematics 193 Cambridge University Press
  • Dai, J., Lathrop, J., Lutz, J., Mayordomo, E., Finite-state dimension (2004) Theoretical Computer Science, 310, pp. 1-33
  • Huffman, D., (1952) A Method for the Construction of Minimum-redundancy Codes, , Institute of Radio Engineers, pages 1098-1102
  • Huffman, D., Canonical forms for information-lossless finite-state logical machines (1959) Transactions on Information Theory, 5 (5), pp. 41-59
  • Lindner, R., Staiger, L., (1977) Algebraische Codierungstheorie-Theorie der Sequentiellen Codierungen, , Akademie-Verlag Berlin
  • Merkle, W., Reimann, J., Selection functions that do not preserve normality (2006) Theory of Computing Systems, 39 (5), pp. 685-697
  • O'Connor, M.G., An unpredictability approach to finite-state randomness (1988) Journal of Computer and System Sciences, 37 (3), pp. 324-336
  • Schnorr, C.P., Stimm, H., Endliche automaten und zufallsfolgen (1972) Acta Informatica, 1, pp. 345-359
  • Shannon, C.E., A mathematical theory of communication (1948) Bell System Technical Journal

Citas:

---------- APA ----------
Becher, V. & Heiber, P.A. (2013) . Normal numbers and finite automata. Theoretical Computer Science, 477, 109-116.
http://dx.doi.org/10.1016/j.tcs.2013.01.019
---------- CHICAGO ----------
Becher, V., Heiber, P.A. "Normal numbers and finite automata" . Theoretical Computer Science 477 (2013) : 109-116.
http://dx.doi.org/10.1016/j.tcs.2013.01.019
---------- MLA ----------
Becher, V., Heiber, P.A. "Normal numbers and finite automata" . Theoretical Computer Science, vol. 477, 2013, pp. 109-116.
http://dx.doi.org/10.1016/j.tcs.2013.01.019
---------- VANCOUVER ----------
Becher, V., Heiber, P.A. Normal numbers and finite automata. Theor Comput Sci. 2013;477:109-116.
http://dx.doi.org/10.1016/j.tcs.2013.01.019