Abstract: 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 such that each word of length at least 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.
Recommendations
Cites work
- A generalization of the self-dual induction to every interval exchange transformation
- Burrows-Wheeler transform and Sturmian words
- Burrows-Wheeler transform of words defined by morphisms
- Characterisations of balanced words via orderings
- Clustering words and interval exchanges
- Episturmian words and some constructions of de Luca and Rauzy
- Episturmian words: a survey
- Extremal values of semi‐regular continuants and codings of interval exchange transformations
- Languages of k -interval exchange transformations
- Recurrence functions of Arnoux-Rauzy sequences, and answer to a question of Morse and Hedlund
- Représentation géométrique de suites de complexité 2n+1
- Structure of K-interval exchange transformations: induction, trajectories, and distance theorems
- Sturmian and Episturmian Words
- Weak mixing and eigenvalues for Arnoux-Rauzy sequences
- Words with simple Burrows-Wheeler transforms
This page was built for publication: Clustering and Arnoux-Rauzy words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6184901)
