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