2023/05/30 by Sébastien Ferenczi, Ferenczi, Sébastien, Luca Q. Zamboni +1 · 1 citation
Computer Science · Mathematics · #68R15 #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Dynamical Systems (math.DS) #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2305.18986
openalex publication_date 2023/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We characterize the clustering of a word under the Burrows-Wheeler transform in terms of the resolution of a bounded number of bispecial factors belonging to the language generated by all its powers. We use this criterion to compute, in every given Arnoux-Rauzy language on three letters, an explicit bound K such that each word of length at least K is not clustering; this bound is sharp for a set of Arnoux-Rauzy languages including the Tribonacci one. In the other direction, we characterize all standard Arnoux-Rauzy clustering words, and all perfectly clustering Arnoux-Rauzy words. We extend some results to episturmian languages, characterizing those which produce infinitely many clustering words, and to larger alphabets.