Least periods of k-automatic sequences

2012/07/23 by Daniel Goč, Jeffrey Shallit, Goc, Daniel +1
Computer Science · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1207.5450

openalex publication_date 2012/07/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Currie and Saari initiated the study of least periods of infinite words, and they showed that every integer n >= 1 is a least period of the Thue-Morse sequence. We generalize this result to show that the characteristic sequence of least periods of a k-automatic sequence is (effectively) k-automatic. Through an implementation of our construction, we confirm the result of Currie and Saari, and we obtain similar results for the period-doubling sequence, the Rudin-Shapiro sequence, and the paperfolding sequence.

Related

• Periodicity, repetitions, and orbits of an automatic sequence
• Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences
• The periodic complexity function of the Thue-Morse word, the Rudin-Shapiro word, and the period-doubling word
• A Class of Automatic Sequences
• Palindromic length complexity and a generalization of Thue-Morse sequences