2025/04/25 by Francesco Dolce, Dolce, Francesco, Hughes, Christian B. · 2 citations
Arts and Humanities · Computer Science · Social Sciences · #37E05 #68R15 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Language and cultural evolution #Syntax, Semantics, Linguistic Variation #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2504.18280
openalex publication_date 2025/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A word over an ordered alphabet is said to be clustering if identical letters appear adjacently in its Burrows-Wheeler transform. Such words are strictly related to (discrete) interval exchange transformations. We use an extended version of the well-known Rauzy induction to show that every return word in the language generated by a regular interval exchange transformation is clustering, partially answering a question of Lapointe (2021).