Navegar

Colección

Datos Estadísticas

Artículo

Alvarez, N.; Becher, V.; Ferrari, P.A.; Yuhjtman, S.A. "Perfect necklaces" (2016) Advances in Applied Mathematics. 80:48-61
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 introduce a variant of de Bruijn words that we call perfect necklaces. Fix a finite alphabet. Recall that a word is a finite sequence of symbols in the alphabet and a circular word, or necklace, is the equivalence class of a word under rotations. For positive integers k and n, we call a necklace (k,n)-perfect if each word of length k occurs exactly n times at positions which are different modulo n for any convention on the starting point. We call a necklace perfect if it is (k,k)-perfect for some k. We prove that every arithmetic sequence with difference coprime with the alphabet size induces a perfect necklace. In particular, the concatenation of all words of the same length in lexicographic order yields a perfect necklace. For each k and n, we give a closed formula for the number of (k,n)-perfect necklaces. Finally, we prove that every infinite periodic sequence whose period coincides with some (k,n)-perfect necklace for some k and some n, passes all statistical tests of size up to k, but not all larger tests. This last theorem motivated this work. © 2016 Elsevier Inc. All rights reserved.

Registro:

Documento: Artículo
Título:Perfect necklaces
Autor:Alvarez, N.; Becher, V.; Ferrari, P.A.; Yuhjtman, S.A.
Filiación:Universidad Nacional Del sur, Argentina
Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, CONICET, Argentina
Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina
Palabras clave:Combinatorics on words; de Bruijn words; Necklaces; Statistical tests of finite size; Statistical tests; Combinatorics on words; De Bruijn; Finite alphabet; Finite size; Infinite periodic sequence; Lexicographic order; Necklaces; Positive integers; Equivalence classes
Año:2016
Volumen:80
Página de inicio:48
Página de fin:61
DOI: http://dx.doi.org/10.1016/j.aam.2016.05.002
Título revista:Advances in Applied Mathematics
Título revista abreviado:Adv. Appl. Math.
ISSN:01968858
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01968858_v80_n_p48_Alvarez

Referencias:

  • Allouche, J.-P., Shallit, J., (2003) Automatic Sequences: Theory, Applications, Generalizations, , Cambridge University Press Cambridge
  • Barbier, E., On suppose écrite la suite naturelle des nombres; Quel est le (1010000) ièmechiffre écrit? (1887) C. R. Séances Acad. Sci. Paris, 105, pp. 1238-1239
  • Barbier, E., On suppose écrite la suite naturelle des nombres; Quel est le (101000) ième chiffre écrit? (1887) C. R. Séances Acad. Sci. Paris, 105, pp. 795-798
  • Becher, V., Heiber, P.A., On extending de Bruijn sequences (2011) Inform. Process. Lett., 111 (18), pp. 930-932
  • Berstel, J., Perrin, D., The origins of combinatorics on words (2007) European J. Combin., 28 (3), pp. 996-1022
  • Borel, É., Les probabilités dénombrables et leurs applications arithmétiques (1909) Rend. Circ. Mat. Palermo, Suppl., 27, pp. 247-271
  • Bugeaud, Y., Distribution Modulo One and Diophantine Approximation (2012) Cambridge Tracts in Mathematics, 193. , Cambridge University Press Cambridge
  • Champernowne, D., The construction of decimals normal in the scale of ten (1933) J. Lond. Math. Soc., 18 S - (4), p. 254
  • Cvetković, D.M., Doob, M., Sachs, H., Spectra of Graphs: Theory and Application (1980) Pure and Applied Mathematics, 87. , Academic Press, Inc., Harcourt Brace Jovanovich, Publishers New York-London
  • De Bruijn, N.G., A combinatorial problem (1946) Proc. K. Ned. Akad. Wet., 49, pp. 758-764. , Indag. Math. 8 1946 461 467
  • Downey, R.G., Hirschfeldt, D.R., (2010) Algorithmic Randomness and Complexity. Theory and Applications of Computability, , Springer New York
  • Harary, F., (1969) Graph Theory, , Addison-Wesley Publishing Co. Reading, Mass.-Menlo Park, Calif.-London
  • Knuth, D.E., (1998) The Art of Computer Programming. Vol. 2: Seminumerical Algorithms, , third edition Addison-Wesley
  • L'Ecuyer, P., Simard, R., TestU01: A C library for empirical testing of random number generators (2007) ACM Trans. Math. Software, 33 (4), p. 40. , Art. 22
  • Lehmann, E.L., (2011) Fisher, Neyman, and the Creation of Classical Statistics, , Springer New York
  • Lothaire, M., Combinatorics on Words (1997) Cambridge Mathematical Library, , Cambridge University Press Cambridge
  • Lothaire, M., Algebraic Combinatorics on Words (2002) Encyclopedia of Mathematics and Its Applications, 90. , Cambridge University Press Cambridge
  • Martin-Löf, P., The definition of random sequences (1966) Inf. Control, 9, pp. 602-619
  • Tutte, W.T., Graph Theory (1984) Encyclopedia of Mathematics and Its Applications, 21. , Addison-Wesley Publishing Company, Advanced Book Program Reading, MA

Citas:

---------- APA ----------
Alvarez, N., Becher, V., Ferrari, P.A. & Yuhjtman, S.A. (2016) . Perfect necklaces. Advances in Applied Mathematics, 80, 48-61.
http://dx.doi.org/10.1016/j.aam.2016.05.002
---------- CHICAGO ----------
Alvarez, N., Becher, V., Ferrari, P.A., Yuhjtman, S.A. "Perfect necklaces" . Advances in Applied Mathematics 80 (2016) : 48-61.
http://dx.doi.org/10.1016/j.aam.2016.05.002
---------- MLA ----------
Alvarez, N., Becher, V., Ferrari, P.A., Yuhjtman, S.A. "Perfect necklaces" . Advances in Applied Mathematics, vol. 80, 2016, pp. 48-61.
http://dx.doi.org/10.1016/j.aam.2016.05.002
---------- VANCOUVER ----------
Alvarez, N., Becher, V., Ferrari, P.A., Yuhjtman, S.A. Perfect necklaces. Adv. Appl. Math. 2016;80:48-61.
http://dx.doi.org/10.1016/j.aam.2016.05.002