dc.creator | Alvarez, Nicolás Alejandro | |
dc.creator | Becher, Veronica Andrea | |
dc.creator | Ferrari, Pablo Augusto | |
dc.creator | Yuhjtman, Sergio Andrés | |
dc.date.accessioned | 2018-06-29T19:50:30Z | |
dc.date.available | 2018-06-29T19:50:30Z | |
dc.date.created | 2018-06-29T19:50:30Z | |
dc.date.issued | 2016-09 | |
dc.identifier | Alvarez, Nicolás Alejandro; Becher, Veronica Andrea; Ferrari, Pablo Augusto; Yuhjtman, Sergio Andrés; Perfect necklaces; Academic Press Inc Elsevier Science; Advances In Applied Mathematics; 80; 9-2016; 48-61 | |
dc.identifier | 0196-8858 | |
dc.identifier | http://hdl.handle.net/11336/50806 | |
dc.identifier | CONICET Digital | |
dc.identifier | CONICET | |
dc.description.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. | |
dc.language | eng | |
dc.publisher | Academic Press Inc Elsevier Science | |
dc.relation | info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0196885816300343 | |
dc.relation | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.aam.2016.05.002 | |
dc.rights | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | |
dc.rights | info:eu-repo/semantics/restrictedAccess | |
dc.subject | Combinatorics on Words | |
dc.subject | De Bruijn Words | |
dc.subject | Necklaces | |
dc.subject | Statistical Tests of Finite Size | |
dc.title | Perfect necklaces | |
dc.type | info:eu-repo/semantics/article | |
dc.type | info:ar-repo/semantics/artículo | |
dc.type | info:eu-repo/semantics/publishedVersion | |