Perfect necklaces
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...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
Academic Press Inc.
2016
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 06920caa a22007577a 4500 | ||
|---|---|---|---|
| 001 | PAPER-15730 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518204631.0 | ||
| 008 | 190411s2016 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-84969245752 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Alvarez, N. | |
| 245 | 1 | 0 | |a Perfect necklaces |
| 260 | |b Academic Press Inc. |c 2016 | ||
| 270 | 1 | 0 | |m Becher, V.; Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, CONICETArgentina; email: vbecher@dc.uba.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Allouche, J.-P., Shallit, J., (2003) Automatic Sequences: Theory, Applications, Generalizations, , Cambridge University Press Cambridge | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Becher, V., Heiber, P.A., On extending de Bruijn sequences (2011) Inform. Process. Lett., 111 (18), pp. 930-932 | ||
| 504 | |a Berstel, J., Perrin, D., The origins of combinatorics on words (2007) European J. Combin., 28 (3), pp. 996-1022 | ||
| 504 | |a Borel, É., Les probabilités dénombrables et leurs applications arithmétiques (1909) Rend. Circ. Mat. Palermo, Suppl., 27, pp. 247-271 | ||
| 504 | |a Bugeaud, Y., Distribution Modulo One and Diophantine Approximation (2012) Cambridge Tracts in Mathematics, 193. , Cambridge University Press Cambridge | ||
| 504 | |a Champernowne, D., The construction of decimals normal in the scale of ten (1933) J. Lond. Math. Soc., 18 S - (4), p. 254 | ||
| 504 | |a 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 | ||
| 504 | |a De Bruijn, N.G., A combinatorial problem (1946) Proc. K. Ned. Akad. Wet., 49, pp. 758-764. , Indag. Math. 8 1946 461 467 | ||
| 504 | |a Downey, R.G., Hirschfeldt, D.R., (2010) Algorithmic Randomness and Complexity. Theory and Applications of Computability, , Springer New York | ||
| 504 | |a Harary, F., (1969) Graph Theory, , Addison-Wesley Publishing Co. Reading, Mass.-Menlo Park, Calif.-London | ||
| 504 | |a Knuth, D.E., (1998) The Art of Computer Programming. Vol. 2: Seminumerical Algorithms, , third edition Addison-Wesley | ||
| 504 | |a 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 | ||
| 504 | |a Lehmann, E.L., (2011) Fisher, Neyman, and the Creation of Classical Statistics, , Springer New York | ||
| 504 | |a Lothaire, M., Combinatorics on Words (1997) Cambridge Mathematical Library, , Cambridge University Press Cambridge | ||
| 504 | |a Lothaire, M., Algebraic Combinatorics on Words (2002) Encyclopedia of Mathematics and Its Applications, 90. , Cambridge University Press Cambridge | ||
| 504 | |a Martin-Löf, P., The definition of random sequences (1966) Inf. Control, 9, pp. 602-619 | ||
| 504 | |a Tutte, W.T., Graph Theory (1984) Encyclopedia of Mathematics and Its Applications, 21. , Addison-Wesley Publishing Company, Advanced Book Program Reading, MA | ||
| 520 | 3 | |a 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. |l eng | |
| 536 | |a Detalles de la financiación: Universidad de Buenos Aires | ||
| 536 | |a Detalles de la financiación: We thank Norberto Fava and Victor Yohai for motivating the question on the existence of periodic sequences that pass any finite family of finite-size tests. We thank Liliana Forzani and Ricardo Fraiman for enlightening discussions. We are grateful to an anonymous referee for the reference to the early work of Ém. Barbier. Alvarez and Becher are members of Laboratoire International Associé INFINIS, Université Paris Diderot–CNRS/Universidad de Buenos Aires–CONICET. Alvarez is supported by CONICET doctoral fellowship. Becher and Ferrari are supported by the University of Buenos Aires and by CONICET . | ||
| 593 | |a Universidad Nacional Del sur, Argentina | ||
| 593 | |a Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, CONICET, Argentina | ||
| 593 | |a Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina | ||
| 690 | 1 | 0 | |a COMBINATORICS ON WORDS |
| 690 | 1 | 0 | |a DE BRUIJN WORDS |
| 690 | 1 | 0 | |a NECKLACES |
| 690 | 1 | 0 | |a STATISTICAL TESTS OF FINITE SIZE |
| 690 | 1 | 0 | |a STATISTICAL TESTS |
| 690 | 1 | 0 | |a COMBINATORICS ON WORDS |
| 690 | 1 | 0 | |a DE BRUIJN |
| 690 | 1 | 0 | |a FINITE ALPHABET |
| 690 | 1 | 0 | |a FINITE SIZE |
| 690 | 1 | 0 | |a INFINITE PERIODIC SEQUENCE |
| 690 | 1 | 0 | |a LEXICOGRAPHIC ORDER |
| 690 | 1 | 0 | |a NECKLACES |
| 690 | 1 | 0 | |a POSITIVE INTEGERS |
| 690 | 1 | 0 | |a EQUIVALENCE CLASSES |
| 700 | 1 | |a Becher, V. | |
| 700 | 1 | |a Ferrari, P.A. | |
| 700 | 1 | |a Yuhjtman, S.A. | |
| 773 | 0 | |d Academic Press Inc., 2016 |g v. 80 |h pp. 48-61 |p Adv. Appl. Math. |x 01968858 |w (AR-BaUEN)CENRE-1218 |t Advances in Applied Mathematics | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-84969245752&doi=10.1016%2fj.aam.2016.05.002&partnerID=40&md5=56a43c2a15bfaed6babefcda368260d3 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.aam.2016.05.002 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_01968858_v80_n_p48_Alvarez |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01968858_v80_n_p48_Alvarez |y Registro en la Biblioteca Digital |
| 961 | |a paper_01968858_v80_n_p48_Alvarez |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 999 | |c 76683 | ||