2024/12/23 by Jeffrey Shallit, Shallit, Jeffrey · 1 citation
Computer Science · #Cellular Automata and Applications #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL)
paper · pdf · doi:10.48550/arxiv.2412.17930
openalex publication_date 2024/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.