Abstract

Fix a finite alphabet. A necklace is a circular word. For positive integers $n$ and $k$, a necklace is $(n,k)$-perfect if all words of length $n$ occur $k$ times but at positions with different congruence modulo $k$ for any convention of the starting position. We define the notion of a Lyndon pair and we use it to construct the lexicographically greatest $(n,k)$-perfect necklace for any $n$ and $k$ such that $n$ divides $k$ or $k$ divides $n$. Our construction generalizes Fredricksen and Maiorana’s construction of the lexicographically greatest de Bruijn sequence of order $n$, based on the concatenation of the Lyndon words whose length divides $n$.

Keywords

Mathematical Subject Classification

Milestones

Authors