Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences

Luke Schaeffer¹ ; Jeffrey Shallit²

¹MIT
²University of Waterloo

The electronic journal of combinatorics, Tome 23 (2016) no. 1

Résumé

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.

Détail

DOI : 10.37236/5752

Classification : 11B85, 68R15
Mots-clés : 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