Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We consider the previously defined notion of finite-state independence and we focus specifically on normal words. We characterize finite-state independence of normal words in three different ways, using three different kinds of asynchronous deterministic finite automata with two input tapes containing infinite words. Based on one of the characterizations we give an algorithm to construct a pair of finite-state independent normal words. © 2019 Elsevier Inc.

Registro:

Documento: Artículo
Título:Finite-state independence and normal sequences
Autor:Álvarez, N.; Becher, V.; Carton, O.
Filiación:ICIC – Universidad Nacional del Sur, CONICET, Departamento de Ciencias en Ingeniería de la Computación, Argentina
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires & ICC, CONICET, Argentina
Institut de Recherche en Informatique Fondamentale, Université Paris Diderot, France
Palabras clave:Agafonov's theorem; Finite transducers; Finite-state automata; Normal numbers; Normal sequences; Computer networks; Finite automata; Systems science; Agafonov's theorem; Deterministic finite automata; Finite state; Finite transducers; Infinite word; Normal numbers; Normal sequences; Number theory
Año:2019
Volumen:103
Página de inicio:1
Página de fin:17
DOI: http://dx.doi.org/10.1016/j.jcss.2019.02.001
Título revista:Journal of Computer and System Sciences
Título revista abreviado:J. Comput. Syst. Sci.
ISSN:00220000
CODEN:JCSSB
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v103_n_p1_Alvarez

Referencias:

  • Agafonov, V.N., Normal sequences and finite automata (1968) Sov. Math. Dokl., 9, pp. 324-325
  • Becher, V., Carton, O., Normal numbers and computer science (2018) Sequences, Groups, and Number Theory, Trends in Mathematics Series, , Valérie Berthé Michel Rigo Birkhäuser/Springer
  • Becher, V., Carton, O., Heiber, P.A., Normality and automata (2015) J. Comput. Syst. Sci., 81 (8), pp. 1592-1613
  • Becher, V., Carton, O., Heiber, P.A., Finite-state independence (2018) Theory Comput. Syst., 62 (7), pp. 1555-1572
  • Becher, V., Figueira, S., Picchi, R., Turing's unpublished algorithm for normal numbers (2007) Theor. Comput. Sci., 377 (1-3), pp. 126-138
  • Becher, V., Heiber, P.A., Slaman, T., A polynomial-time algorithm for computing absolutely normal numbers (2013) Inf. Comput., 232, pp. 1-9
  • Borel, É., Les probabilités dénombrables et leurs applications arithmétiques (1909) Rend. Circ. Mat. Palermo, 27, pp. 247-271
  • Bugeaud, Y., Distribution Modulo One and Diophantine Approximation (2012) Cambridge Tracts in Mathematics, 193. , Cambridge University Press
  • Carton, O., Heiber, P.A., Normality and two-way automata (2015) Inf. Comput., 241, pp. 264-276
  • Champernowne, D., The construction of decimals normal in the scale of ten (1933) J. Lond. Math. Soc., s1–8 (4), pp. 254-260
  • Dai, J., Lathrop, J., Lutz, J., Mayordomo, E., Finite-state dimension (2004) Theor. Comput. Sci., 310, pp. 1-33
  • Hardy, G.H., Wright, E.M., An Introduction to the Theory of Numbers (2008), sixth edition Oxford University Press Oxford; Kuipers, L., Niederreiter, H., Uniform Distribution of Sequences (1974), Wiley-Interscience New York; Lutz, J., Mayordomo, E., Computing absolutely normal numbers in nearly linear time (2016); Perrin, D., Pin, J.-É., Infinite Words (2004), Elsevier; Pin, J.-E., Relational Morphisms, Transductions and Operations on Languages (1989), pp. 34-55. , Springer Berlin Heidelberg Berlin, Heidelberg; Sakarovitch, J., Elements of Automata Theory (2009), Cambridge University Press; Schnorr, C.P., Stimm, H., Endliche Automaten und Zufallsfolgen (1972) Acta Inform., 1, pp. 345-359
  • Senata, E., Non-negative Matrices and Markov Chains (2006), Springer; Turing, A., A note on normal numbers (1992) Collected Works of A.M. Turing: Pure Mathematics, pp. 117-119. , J.L. Britton North Holland Amsterdam with notes of the editor in 263–265
  • Wall, D.D., Normal Numbers (1949), PhD thesis University of California Berkeley, California

Citas:

---------- APA ----------
Álvarez, N., Becher, V. & Carton, O. (2019) . Finite-state independence and normal sequences. Journal of Computer and System Sciences, 103, 1-17.
http://dx.doi.org/10.1016/j.jcss.2019.02.001
---------- CHICAGO ----------
Álvarez, N., Becher, V., Carton, O. "Finite-state independence and normal sequences" . Journal of Computer and System Sciences 103 (2019) : 1-17.
http://dx.doi.org/10.1016/j.jcss.2019.02.001
---------- MLA ----------
Álvarez, N., Becher, V., Carton, O. "Finite-state independence and normal sequences" . Journal of Computer and System Sciences, vol. 103, 2019, pp. 1-17.
http://dx.doi.org/10.1016/j.jcss.2019.02.001
---------- VANCOUVER ----------
Álvarez, N., Becher, V., Carton, O. Finite-state independence and normal sequences. J. Comput. Syst. Sci. 2019;103:1-17.
http://dx.doi.org/10.1016/j.jcss.2019.02.001