2025/03/02 by Aleksi Saarela, Saarela, Aleksi · 1 citation
Computer Science · #68R15 #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Natural Language Processing Techniques
paper · pdf · doi:10.48550/arxiv.2503.00960
openalex publication_date 2025/03/02 · openalex created_date 2025/10/12 · openalex updated_date 2026/07/28
We characterize the words that can be mapped to arbitrarily high powers by injective morphisms. For all other words, we prove a linear upper bound for the highest power that they can be mapped to, and this bound is optimal up to a constant factor if there is no restriction on the size of the alphabet. We also prove that, for any integer n ≥ 2, deciding whether a given word can be mapped to an nth power by a nonperiodic morphism is NP-hard and in PSPACE, and so is deciding whether a given word can be mapped to a nonprimitive word by a nonperiodic morphism.