Lyndon pairs and the lexicographically greatest perfect necklace

Abstract

Fijemos un alfabeto finito. Un collar es una palabra circular. Para los enteros positivos n y k, un collar es (n,k)-perfecto si todas las palabras de longitud n aparecen k veces pero en posiciones con diferente congruencia módulo k para cualquier convención de la posición inicial. Definimos la noción de un par Lyndon y la usamos para construir el collar (n,k)-perfecto lexicográficamente más grande para cualquier n y k tal que n divida a k o k divida a n. Nuestra construcción generaliza la construcción de Fredricksen y Maiorana de la secuencia de De Bruijn lexicográficamente más grande de orden n, basada en la concatenación de las palabras Lyndon cuya longitud divida a n.