This analysis reveals linear upper bounds for certain words' powers, indicating NP-hardness for nonperiodic morphisms.
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.
No takes yet. Share an insight, caveat, or question.
Aleksi Saarela (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: