Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.19619 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |