ML p(r)ior | Perfect Necklaces

Perfect Necklaces

2016-01-29
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 any n, passes all statistical tests of size up to k, but not all larger tests. This last theorem motivated this work.
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2018-10-29
1810.12275 | math.CO

An abelian anti-power of order $k$ (or simply an abelian $k$-anti-power) is a concatenation of $k$ c… show more
PDF

Highlights - Most important sentences from the article

2018-12-18
1812.07330 | cs.DM

Two words are $k$-binomially equivalent whenever they share the same subwords, i.e., subsequences, o… show more
PDF

Highlights - Most important sentences from the article

2019-03-13

We consider a certain natural generalization of de Bruijn words, and use it to compute the exact max… show more
PDF

Highlights - Most important sentences from the article

2019-04-22
1904.10028 | math.CO

Rich words are characterized by containing the maximum possible number of distinct palindromes. Seve… show more
PDF

Highlights - Most important sentences from the article

2019-04-25
1904.11334 | cs.DM

A two-dimensional ($2$D) word is a $2$D palindrome if it is equal to its reverse and it is an HV-pal… show more
PDF

Highlights - Most important sentences from the article

2018-10-25

We study the factor complexity and closure properties of automatic sequences based on Parry or Bertr… show more
PDF

Highlights - Most important sentences from the article

2019-03-30
1904.00248 | cs.DM

The length $a(n)$ of the longest common subsequence of the $n$'th Thue-Morse word and its bitwise co… show more
PDF

Highlights - Most important sentences from the article

2018-07-19
1807.07208 | cs.FL

In this paper we consider the notion of normality of sequences in shifts of finite type. A sequence … show more
PDF

Highlights - Most important sentences from the article

2018-07-22
1807.08321 | math.DS

Given an infinite word $w$ from a uniquely ergodic subshift $L$, we can associate to it a number $\n… show more
PDF

Highlights - Most important sentences from the article

2017-05-24
1705.08747 | cs.FL

The second author introduced with I. T\"orm\"a a two-player word-building game [Playing with Subshif… show more
PDF

Highlights - Most important sentences from the article

2017-12-15

We present a new recursive generation algorithm for prefix normal words. These are binary strings wi… show more
PDF

Highlights - Most important sentences from the article

2018-04-09

We give metric theorems for the property of Borel normality for real numbers under the assumption of… show more
PDF

Highlights - Most important sentences from the article

2019-06-09
1906.03689 | cs.DM

We show that the number of length-$n$ words over a $k$-letter alphabet having no even palindromic pr… show more
PDF

Highlights - Most important sentences from the article

2014-04-01

A prefix normal word is a binary word with the property that no substring has more 1s than the prefi… show more
PDF

Highlights - Most important sentences from the article

2015-10-02

Constantinescu and Ilie (Bulletin of the EATCS 89, 167-170, 2006) introduced the idea of an Abelian … show more
PDF

Highlights - Most important sentences from the article

2016-01-18

A cost Markov chain is a Markov chain whose transitions are labelled with non-negative integer costs… show more
PDF

Highlights - Most important sentences from the article

2018-01-26
1801.08707 | cs.LO

Let $\frac{p}{q}$ be a rational number. Numeration in base $\frac{p}{q}$ is defined by a function th… show more