Mapped Exponent and Asymptotic Critical Exponent of Words

2025/06/04 by Foster, Eva, Aleksi Saarela, Saarela, Aleksi +2 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #68R15 #Algorithms and Data Compression #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2506.04091

openalex publication_date 2025/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study how much injective morphisms can increase the repetitiveness of a given word. This question has a few possible variations depending on the meaning of ``repetitiveness''. We concentrate on fractional exponents of finite words and asymptotic critical exponents of infinite words. We characterize finite words that, when mapped by injective morphisms, can have arbitrarily high fractional exponent. For infinite words, alongside other results, we show that the asymptotic critical exponent grows at most by a constant factor (depending on the size of the alphabet) when mapped by an injective morphism. For both finite and infinite words, the binary case is better understood than the general case.

Citations

• Mapping words to powers by morphisms
• Critical exponent of binary words with few distinct palindromes
• For each α > 2 there is an infinite binary word with critical exponent α
• Sturmian words and words with a critical exponent

Cited by

• The limit of repetition thresholds of rich sequences

Related

• Critical exponent of binary words with few distinct palindromes
• The Lexicographically Least Binary Rich Word Achieving the Repetition Threshold
• The asymptotic repetition threshold of sequences rich in palindromes
• For each α > 2 there is an infinite binary word with critical exponent α
• Mapping words to powers by morphisms