Mapping words to powers by morphisms
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915179300651008 |
|---|---|
| author | Saarela, Aleksi |
| author_facet | Saarela, Aleksi |
| contents | 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 \geq 2$, deciding whether a given word can be mapped to an $n$th 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_00960 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Mapping words to powers by morphisms Saarela, Aleksi Formal Languages and Automata Theory Combinatorics 68R15 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 \geq 2$, deciding whether a given word can be mapped to an $n$th 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. |
| title | Mapping words to powers by morphisms |
| topic | Formal Languages and Automata Theory Combinatorics 68R15 |
| url | https://arxiv.org/abs/2503.00960 |