Runs in Paperfolding Sequences
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914381653082112 |
|---|---|
| author | Shallit, Jeffrey |
| author_facet | Shallit, Jeffrey |
| contents | The paperfolding sequences form an uncountable class of infinite sequences over the alphabet $\{ -1, 1 \}$ that describe the sequence of folds arising from iterated folding of a piece of paper, followed by unfolding. In this note we observe that the sequence of run lengths in such a sequence, as well as the starting and ending positions of the $n$'th run, is $2$-synchronized and hence computable by a finite automaton. As a specific consequence, we obtain the recent results of Bunder, Bates, and Arnold, in much more generality, via a different approach. We also prove results about the critical exponent and subword complexity of these run-length sequences. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_17930 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Runs in Paperfolding Sequences Shallit, Jeffrey Combinatorics Discrete Mathematics Formal Languages and Automata Theory The paperfolding sequences form an uncountable class of infinite sequences over the alphabet $\{ -1, 1 \}$ that describe the sequence of folds arising from iterated folding of a piece of paper, followed by unfolding. In this note we observe that the sequence of run lengths in such a sequence, as well as the starting and ending positions of the $n$'th run, is $2$-synchronized and hence computable by a finite automaton. As a specific consequence, we obtain the recent results of Bunder, Bates, and Arnold, in much more generality, via a different approach. We also prove results about the critical exponent and subword complexity of these run-length sequences. |
| title | Runs in Paperfolding Sequences |
| topic | Combinatorics Discrete Mathematics Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2412.17930 |