Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences

Luke Schaeffer, Jeffrey Shallit

Abstract


We prove that the property of being closed (resp., palindromic, rich, privileged trapezoidal, balanced) is expressible in first-order logic for automatic (and some related) sequences. It therefore follows that the characteristic function of those $n$ for which an automatic sequence $\bf x$ has a closed (resp., palindromic, privileged, rich, trapezoidal, balanced) factor of length  $n$ is itself automatic. For privileged words this requires a new characterization of the privileged property. We compute the corresponding characteristic functions for various famous sequences, such as the Thue-Morse sequence, the Rudin-Shapiro sequence, the ordinary  paperfolding sequence, the period-doubling sequence, and the Fibonacci sequence. Finally, we also show that the function counting the total number of palindromic factors in the prefix of length $n$ of a $k$-automatic sequence is not $k$-synchronized.


Keywords


Decision procedure, Closed word, Palindrome, Rich word, Privileged word, Trapezoidal word, Balanced word, Thue-Morse sequence, Rudin-Shapiro sequence, Period-doubling sequence, Paperfolding sequence, Fibonacci word

Full Text: PDF