Word Chain Generators for Prefix Normal Words
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911124990984192 |
|---|---|
| author | Adamson, Duncan Dudey, Moritz Fleischmann, Pamela Huch, Annika |
| author_facet | Adamson, Duncan Dudey, Moritz Fleischmann, Pamela Huch, Annika |
| contents | In 2011, Fici and Lipták introduced prefix normal words. A binary word is prefix normal if it has no factor (substring) that contains more occurrences of the letter 1 than the prefix of the same length. Among the open problems regarding this topic are the enumeration of prefix normal words and efficient testing methods. We show a range of characteristics of prefix normal words. These include properties of factors that are responsible for a word not being prefix normal. With word chains and generators, we introduce new ways of relating words of the same length to each other. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_19619 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Word Chain Generators for Prefix Normal Words Adamson, Duncan Dudey, Moritz Fleischmann, Pamela Huch, Annika Combinatorics Computation and Language In 2011, Fici and Lipták introduced prefix normal words. A binary word is prefix normal if it has no factor (substring) that contains more occurrences of the letter 1 than the prefix of the same length. Among the open problems regarding this topic are the enumeration of prefix normal words and efficient testing methods. We show a range of characteristics of prefix normal words. These include properties of factors that are responsible for a word not being prefix normal. With word chains and generators, we introduce new ways of relating words of the same length to each other. |
| title | Word Chain Generators for Prefix Normal Words |
| topic | Combinatorics Computation and Language |
| url | https://arxiv.org/abs/2508.19619 |